연결 리스트(Linked List)란?
연결 리스트는 각 노드가 두 개의 블록으로 구성된 선형 자료구조입니다. 한쪽 블록에는 노드의 값(데이터)이 저장되고, 다른 블록에는 다음 노드를 가리키는 주소가 저장됩니다.
여기서 각 노드가 리스트 내의 다른 노드를 가리키는 포인터를 하나씩 갖고 있는 연결 리스트가 있다고 가정해 보겠습니다. 이때 과제는 두 연결 리스트가 서로 교차하는 노드를 찾는 것입니다. 만약 두 리스트가 교차하지 않는다면 결과로 NULL 또는 빈 값을 반환하면 됩니다.
예시 1
입력:
출력:
2
설명: 주어진 연결 리스트는 값이 '2'인 노드에서 서로 교차하기 때문에, 출력값으로 '2'를 반환합니다.
예시 2
입력:
출력:
NULL
설명: 두 리스트 사이에 공통되는 지점이 없으므로 이 경우에는 NULL을 반환합니다.
문제 해결 접근 방법
두 연결 리스트는 공통 지점에서 서로 교차하고 있습니다. 교차 지점을 찾으려면 두 리스트를 모두 순회하면서 두 포인터가 동일한 노드를 가리키는 순간을 확인하면 됩니다. 교차 지점 이후에는 두 리스트가 완전히 같은 경로를 따라가기 때문에, 반드시 next 포인터가 같은 노드를 가리키는 시점이 존재합니다. 그 지점의 값을 반환하면 됩니다.
- 데이터와 다음 노드를 가리키는 포인터를 가진 두 개의 연결 리스트를 준비합니다.
- commonPoint(listnode* headA, listnode* headB) 함수는 두 연결 리스트의 헤드 포인터를 각각 인자로 받아, 두 리스트의 교차 지점(공통 노드)의 값을 반환합니다.
- 연결 리스트의 길이를 계산하는 정수형 함수는 리스트의 헤드부터 시작하여 두 리스트의 길이를 각각 구해 반환합니다.
- 두 리스트의 헤드에 포인터를 만든 뒤, 길이가 더 긴 리스트의 포인터를 (첫 번째 리스트 길이 − 두 번째 리스트 길이)만큼 먼저 전진시킵니다.
- 그다음 두 리스트를 동시에 순회하면서 next 포인터가 같아지는 지점을 찾습니다.
- 두 리스트가 교차하는 해당 노드의 값을 최종적으로 반환합니다.
Java 구현 예제
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에서 서로 교차합니다.
