Today I Learned

오늘도 코테코테..

160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/

문제

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.

해결방법 & Java 코드

• 투포인터로 해결이 가능한 문제다.

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

        ListNode a = headA;
        ListNode b = headB;

        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }

        return a;
    }

• while문 안에서 a와 b는 next로 한칸씩 전진한다. while문은 a==b가될 때 까지 진행된다.

• a가 끝까지 가서 null이 되면 headB로 이동하고, b가 null이되면 headA로 이동한다. 그렇게 계속 while문을 돌다보면 교차점에서 만나게 된다. 만약 만나지 않는다면 둘이 동시에 null이 되는 지점에서 반환된다.