160. 相交链表

160. 相交链表

题解

哈希表

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

双指针

来源：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/

• 头节点 headA 到 node 前，共有 a−c 个节点；
• 头节点 headB 到 node 前，共有 b−c 个节点；

考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：

• 指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：a + (b - c)
• 指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：b + (a - c)

如下式所示，此时指针 A , B 重合，并有两种情况：a + (b - c) = b + (a - c)

• 若两链表 有 公共尾部 (即 c > 0) ：指针 A , B 同时指向「第一个公共节点」node 。
• 若两链表 无 公共尾部 (即 c = 0) ：指针 A , B 同时指向 null。

如下图所示，为 a = 5, b = 3, c = 2 示例的算法执行过程。

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while (A != B) {
            A = (A == null ? headB : A.next);
            B = (B == null ? headA : B.next);
        }
        return A;
    }
}