연결 리스트(Linked List)란?
연결 리스트는 각 노드가 두 개의 부분으로 구성된 선형 자료구조입니다. 하나의 부분에는 노드의 값 또는 데이터가 저장되고, 다른 부분에는 다음 노드의 주소가 저장됩니다.
이번 문제에서는 각 노드가 리스트 내의 다른 노드를 가리킬 수 있는 연결 리스트가 주어진다고 가정합니다. 우리의 과제는 두 연결 리스트가 서로 교차하는 지점의 노드를 찾는 것입니다. 만약 두 리스트가 교차하지 않는다면 NULL 또는 빈 값을 결과로 반환해야 합니다.
문제 예시
입력 예시 1
출력:
2
설명: 주어진 두 연결 리스트가 값 '2'를 가진 노드에서 교차하므로, '2'를 출력으로 반환합니다.
입력 예시 2
출력:
NULL
설명: 두 리스트 사이에 공통되는 지점이 없으므로, 이 경우에는 NULL을 반환합니다.
문제 해결 접근 방식
두 연결 리스트는 서로 교차하는 공통 지점을 가지고 있습니다. 교차 지점을 찾기 위해서는 두 리스트를 순회하면서 두 포인터가 동일한 노드를 가리키는 시점을 찾으면 됩니다. 리스트의 길이가 다르기 때문에, 먼저 길이 차이만큼 긴 리스트의 포인터를 앞당긴 후 함께 순회하면 두 포인터는 반드시 같은 노드에서 만나게 됩니다. 그 지점의 값을 반환하면 됩니다.
- 데이터와 다음 노드를 가리키는 포인터를 가진 두 개의 연결 리스트를 준비합니다.
commonPoint(listnode* headA, listnode* headB)함수는 두 연결 리스트의 헤드 포인터를 각각 전달받아, 두 리스트의 공통 교차 지점에 해당하는 노드의 값을 반환합니다.- 연결 리스트의 길이를 계산하는 정수형 함수가 리스트의 헤드부터 끝까지 순회하며 각 리스트의 길이를 반환합니다.
- 두 리스트의 헤드를 가리키는 포인터를 각각 생성한 뒤, 더 긴 쪽 리스트를 (첫 번째 리스트 길이 − 두 번째 리스트 길이)만큼 먼저 전진시킵니다.
- 이후 두 포인터가 가리키는 노드가 동일해지는 시점까지 두 리스트를 동시에 순회합니다.
- 두 리스트가 교차하는 해당 노드의 값을 최종적으로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class listnode {
public:
int data;
listnode * next;
};
// 연결 리스트의 길이를 구하는 함수
int count(listnode * head) {
int count = 0;
while (head != NULL) {
count++;
head = head -> next;
}
return count;
}
// 두 연결 리스트의 교차 지점을 구하는 함수
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
설명: 첫 번째 리스트(A)는 5 → 7 → 3 순서로, 두 번째 리스트(B)는 4 → 9 → 2 → 7 → 3 순서로 구성되어 있으며, 두 리스트는 값 '7'을 가진 노드에서 합쳐집니다. 따라서 교차 지점의 값인 7이 출력됩니다.
