Linked List는 각 노드에 두 개의 블록이 있는 선형 데이터 구조로, 한 블록에는 노드의 값 또는 데이터가 포함되고 다른 블록에는 다음 필드의 주소가 포함됩니다.
각 노드에 목록의 다른 노드를 가리키는 임의의 포인터가 포함된 연결 목록이 있다고 가정해 보겠습니다. 작업은 두 연결 목록이 서로 교차하는 노드를 찾는 것입니다. 교차하지 않으면 NULL을 반환하거나 출력으로 비어 있습니다.
예를 들어
입력-1:
<강한> 
출력:
2
설명: 주어진 연결 리스트는 '2' 값을 가진 노드에서 교차하므로 '2' 값을 출력으로 반환합니다.
입력-2:
<강한> 
출력:
NULL
설명: 공통점이 없으므로 이 경우 NULL을 반환합니다.
이 문제를 해결하기 위한 접근 방식
서로 교차하는 공통점이 있는 두 개의 연결 목록이 있습니다. 교차점을 찾기 위해 우리는 두 연결 리스트가 같은 값을 똑같이 가리키고 있다는 것을 찾을 때까지 두 연결 리스트를 탐색할 것입니다. 어느 시점에서 연결 리스트의 다음 노드에 대한 포인터는 동일할 것입니다. 따라서 해당 포인트의 값을 반환합니다.
- 데이터가 있는 두 개의 연결 목록을 가져오고 다음 노드에 대한 포인터를 가져옵니다.
- commonPoint(listnode*headA, listnode*headB) 함수는 연결 목록의 두 포인터를 각각 가져와 연결 목록의 공통 또는 교차점 값을 반환합니다.
- 연결 목록의 길이를 찾는 정수 함수는 목록의 선두에서 두 연결 목록의 길이를 반환합니다.
- 이제 두 목록의 헤드에 대한 포인터를 만들고 길이가 더 긴 목록을 탐색합니다(첫 번째 목록의 길이 – 두 번째 목록의 길이).
- 다음 포인터가 같을 때까지 목록을 탐색합니다.
- 두 목록이 교차하는 특정 노드의 값을 반환합니다.
예
public class Solution {
static listnode headA,
headB;
static class listnode {
int data;
listnode next;
listnode(int d) {
data = d;
next = null;
}
}
int count(listnode head) {
int c = 0;
while (head != null) {
c++;
head = head.next;
}
return c;
}
int commonPoint(listnode headA, listnode headB) {
listnode p1 = headA;
listnode p2 = headB;
int c1 = count(headA);
int c2 = count(headB);
if (c1 > c2) {
for (int i = 0; i < c1 - c2; i++) {
if (p1 == null) {
return - 1;
}
p1 = p1.next;
}
}
if (c1 < c2) {
for (int i = 0; i < c2 - c1; i++) {
if (p2 == null) {
return - 1;
}
p2 = p2.next;
}
}
while (p1 != null && p2 != null) {
if (p1.data == p2.data) {
return p1.data;
}
p1 = p1.next;
p2 = p2.next;
}
return - 1;
}
public static void main(String[] args) {
Solution list = new Solution();
list.headA = new listnode(5);
list.headA.next = new listnode(4);
list.headA.next.next = new listnode(9);
list.headA.next.next.next = new listnode(7);
list.headA.next.next.next.next = new listnode(1);
list.headB = new listnode(6);
list.headB.next = new listnode(7);
list.headB.next.next = new listnode(1);
System.out.println(list.commonPoint(headA, headB));
}
} 위의 코드를 실행하면 다음과 같이 출력이 생성됩니다.
출력
7
설명 :주어진 연결 리스트가 7에서 교차합니다.
