Linked List는 각 노드에 두 개의 블록이 있는 선형 데이터 구조로, 한 블록에는 노드의 값 또는 데이터가 포함되고 다른 블록에는 다음 필드의 주소가 포함됩니다.
각 노드에 목록의 다른 노드를 가리키는 임의의 포인터가 포함된 연결 목록이 있다고 가정해 보겠습니다. 작업은 두 연결 목록이 서로 교차하는 노드를 찾는 것입니다. 교차하지 않으면 NULL을 반환하거나 출력으로 비어 있습니다.
예를 들어
입력-1:
<강한> 
출력:
2
설명: 주어진 연결 리스트가 '2' 값을 갖는 노드에서 교차하므로 출력으로 '2' 값을 반환합니다.
입력-2:
<강한> 
출력:
NULL
설명: 공통점이 없으므로 이 경우 NULL을 반환합니다.
이 문제를 해결하기 위한 접근 방식
서로 교차하는 공통점이 있는 두 개의 연결 목록이 있습니다. 교차점을 찾기 위해 우리는 두 연결 리스트가 같은 값을 똑같이 가리키고 있다는 것을 찾을 때까지 두 연결 리스트를 탐색할 것입니다. 어느 시점에서 연결 리스트의 다음 노드에 대한 포인터는 동일할 것입니다. 따라서 해당 포인트의 값을 반환합니다.
- 데이터가 있는 두 개의 연결 목록을 가져오고 다음 노드에 대한 포인터를 가져옵니다.
- commonPoint(listnode*headA, listnode*headB) 함수는 연결 목록의 두 포인터를 각각 가져와 연결 목록의 공통 또는 교차점 값을 반환합니다.
- 연결 목록의 길이를 찾는 정수 함수는 목록의 선두에서 두 연결 목록의 길이를 반환합니다.
- 이제 두 목록의 헤드에 대한 포인터를 만들고 길이가 더 긴 목록을 탐색합니다(첫 번째 목록의 길이 – 두 번째 목록의 길이).
- 다음 포인터가 같을 때까지 목록을 탐색합니다.
- 두 목록이 교차하는 특정 노드의 값을 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
class listnode {
public:
int data;
listnode * next;
};
// Find the length of the linked list
int count(listnode * head) {
int count = 0;
while (head != NULL) {
count++;
head = head -> next;
}
return count;
}
//Function to get the common point of two linked list
int commonPoint(listnode * headA, listnode * headB) {
int len1 = count(headA);
int len2 = count(headB);
listnode * p1 = headA;
listnode * p2 = headB;
if (len1 > len2) {
for (int i = 0; i < len1 - len2; ++i) {
p1 = p1 -> next;
}
}
if (len1 < len2) {
for (int i = 0; i < len2 - len1; ++i) {
p2 = p2 -> next;
}
}
while (p1 != NULL and p2 != NULL) {
if (p1 == p2) {
return p1 -> data;
}
p1 = p1 -> next;
p2 = p2 -> next;
}
return -1;
}
int main() {
listnode * head;
listnode * headA = new listnode();
headA -> data = 5;
listnode * headB = new listnode();
headB -> data = 4;
head = new listnode();
head -> data = 9;
headB -> next = head;
head = new listnode();
head -> data = 2;
headB -> next -> next = head;
head = new listnode();
head -> data = 7;
headA -> next = head;
headB -> next -> next -> next = head;
head = new listnode();
head -> data = 3;
headA -> next -> next = head;
headA -> next -> next -> next = NULL;
cout << commonPoint(headA, headB) << endl;
} 위의 코드를 실행하면 출력이 다음과 같이 생성됩니다.
출력
7
설명: 주어진 연결 목록은 '7'에서 병합됩니다.
