[LeethCode] 160번 Intersection of Two Linked Lists

Intersection of Two Linked Lists

문제 설명

- 두 개의 단방향 연결 리스트 headA와 headB가 주어집니다.
- 두 리스트가 어떤 위치에서든 교차할 수 있습니다. 즉, 특정 노드 이후부터 두 리스트가 동일한 노드들을 공유하게 될 수 있습니다.
- 이 문제에서 교차점이란 두 리스트가 연결되어 동일한 노드들이 뒤따르는 시작 지점을 의미합니다.
- 교차점이 없는 경우 null을 반환합니다.

예시

1. 예제1

1) 입력 : headA = [4,1,8,4,5], headB = [5, 6, 1, 8, 4, 5]
2) 출력: 교차 노드 값이 8

2. 예제2

1) 입력: headA = [2,6,4], headB = [1,5]
2) 출력: null (교차 없음)

해결방법

투 포인터를 사용합니다.

1. 포인터 설정

1) 포인터 nodeA를 리스트 headA의 시작 지점에 두고, 포인터 nodeB를 리스트 headB의 시작 지점에 둡니다.

2. 포인터 이동

1) 두 포인터가 각각 headA와 headB를 끝까지 순회한 뒤에도 교차점이 발견되지 않았다면, 투 포인터를 서로 반대 리스트의 시작 지점으로 이동합니다.
2) 즉, nodeA가 headA의 끝에 도달하면 nodeB의 시작으로, nodeB가 headB의 끝에 도달하면 nodeA의 시작으로 이동하게 합니다.

3. 교차점 발견

1) 투 포인터가 교차점에서 만나게 되면 해당 위치의 노드를 반환합니다.
2) 만약 끝까지 탐색해도 투 포인터가 만나지 않는다면 교차점이 없다는 뜻이므로 null을 반환합니다.

코드

package easy.intersectionOfTwoLinkedList;

public class Solution {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode nodeA = headA;
        ListNode nodeB = headB;

        while (nodeA != nodeB) {
            nodeA = (nodeA == null) ? headB : nodeA.next;
            nodeB = (nodeB == null) ? headA : nodeB.next;
        }
        return nodeA;
    }

    public static void main(String[] args) {
        // 교차 노드를 생성합니다.
        ListNode intersection = new ListNode(8);
        intersection.next = new ListNode(4);
        intersection.next.next = new ListNode(5);

        // listA를 생성하고 교차 노드에 연결합니다.
        ListNode listA = new ListNode(4);
        listA.next = new ListNode(1);
        listA.next.next = intersection;

        // listB를 생성하고 교차 노드에 연결합니다.
        ListNode listB = new ListNode(5);
        listB.next = new ListNode(6);
        listB.next.next = new ListNode(1);
        listB.next.next.next = intersection;

        Solution solution = new Solution();
        ListNode node = solution.getIntersectionNode(listA, listB);
        System.out.println(node != null ? node.val : "No intersection");
    }
}

예시1 테이블

포인터	1단계	2단계	3단계	4단계	5단계	6단계	7단계	8단계	9단계	10단계
nodeA	4	1	8	4	5	null	5	6	1	8
nodeB	5	6	1	8	4	5	null	4	1	8

설명

1. 1단계: nodeA는 listA의 첫 번째 노드 4, nodeB는 listB의 첫 번째 노드 5를 가리킵니다.
2. 2단계: nodeA는 1, nodeB는 6을 가리킵니다.
3. 3단계: nodeA는 8, nodeB는 1을 가리킵니다.
4. 4단계: nodeA는 4, nodeB는 8을 가리킵니다.
5. 5단계: nodeA는 5, nodeB는 4를 가리킵니다.
6. 6단계: nodeA가 listA의 끝에 도달하여 null이 되고, nodeB는 5를 가리킵니다.
7. 7단계: nodeA는 listB의 시작으로 이동하여 5를 가리키고, nodeB는 null이 됩니다.
8. 8단계: nodeA는 6, nodeB는 listA의 시작으로 이동하여 4를 가리킵니다.
9. 9단계: nodeA는 1, nodeB는 1을 가리킵니다.(값이 동일해도, 객체가 동일하지 않음)
10. 10단계: nodeA와 nodeB가 8에서 만나므로, 교차점을 찾게 되어 탐색이 종료됩니다.

이제 교차점 노드 8에서 두 포인터가 만나므로, 이 노드가 두 리스트의 교차점입니다.

예시2 테이블

포인터	1단계	2단계	3단계	4단계	5단계	6단계	7단계
nodeA	2	6	4	null	1	5	null
nodeB	1	5	null	2	6	4	null

설명

1. 1단계: nodeA는 listA의 첫 번째 노드 2를 가리키고, nodeB는 listB의 첫 번째 노드 1을 가리킵니다.
2. 2단계: nodeA와 nodeB 모두 각각 다음 노드로 이동하여 nodeA는 6, nodeB는 5를 가리킵니다.
3. 3단계: nodeA는 4로 이동하고, nodeB는 listB의 끝에 도달하여 null이 됩니다.
4. 4단계: nodeA가 null이 되어 listB의 시작 2로 이동하고, nodeB는 listA의 시작 2로 이동합니다.
5. 5단계: nodeA는 6, nodeB는 6으로 다음 노드로 이동합니다.
6. 6단계: nodeA와 nodeB 모두 각각 다음 노드로 이동하여 nodeA는 5, nodeB는 4를 가리킵니다.
7. 7단계: nodeA와 nodeB는 동시에 null이 되어 종료됩니다.

이제 두 포인터가 동시에 null에 도달하여 교차점이 없음을 확인하게 됩니다.