160. Intersection of Two Linked Lists

Leetcode Linked List Two Pointers

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in $O(n)$ time and use only $O(1)$ memory.

分析

遍历其中一个链表，把链表节点存储在哈希表中。然后在遍历另一个链表时，检查节点node是否在哈希表中：如果存在，则node就是公共节点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    Set<ListNode> set = new HashSet<>();
    while (headA != null) {
        set.add(headA);
        headA = headA.next;
    }
    while (headB != null) {
        if (set.contains(headB)) return headB;
        else headB = headB.next;
    }
    return null;
}

使用两个指针，每个指针指向一个链表头部。然后使用指针遍历链表，达到链表尾部后，遍历另一个链表，直到链表尾部。如果存在交叉，那么这两个指针在第二次遍历以后肯定会相遇。即pointA = pointB，如果直到遍历结束，还没有相遇，即没有交叉。题目不要求一定相交。

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

    // trick: The number of iteration will be at most one.
    // If the two linked lists have no intersection at all,
    // posA and posA will be null at the same time,
    // and then jump out of the iteration to return a null.
    while (posA != posB) {
        posA = (posA == null)? headB : posA.next;
        posB = (posB == null)? headA : posB.next;
    }
    return posA;
}