Leetcode_hot100_160.相交链表

题目要求

  • 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

解题思路

  • 设第一条链表长度为x + z，第二条链表长度为y + z，其中z为两链表相交部分的长度。

注意到：（x + z）+ y = （y + z）+ x

  • 从 a1a_1 出发的指针，走到空节点时让它下一步跳到 b1b_1
  • 从 b1b_1 出发的指针，走到空节点时让它下一步跳到 a1a_1

如上图：

  • 从 a1a_1 出发的指针，走了 x + z + y = 9 步后到达 c1c_1
  • 从 b1b_1 出发的指针，走了 y + z + x = 9 步后到达 c1c_1

如果两条链表不相交
因为 a2a_2 和 b3b_3 的下一个节点都是空节点，可以视作在空节点相交

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while(A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }

        return A;
    }
}
  • 时间复杂度：O(m + n)。
  • 空间复杂度：O(1)。