WangBa's Blog

0160. Intersection of Two Linked Lists

LeetCode真的难系列

发布于：2020年10月12日
次浏览

160. 相交链表 Easy

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

img

在节点 c1 开始相交。

示例 1：

img

1
2
3
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

img

1
2
3
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

img

1
2
3
4
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路分析

思路一：暴力法

遍历链表 A 的时候，每遍历一个结点都完整遍历一下链表 B，判断指向的结点是否为同一个，这样时间复杂度为 O(mn)

思路二：+ HashMap

在思路一的基础上，先将链表 A 的所有结点先放入 HashMap 中，遍历链表 B 的时候比较每个节点是否存在 HashMap 中，此时时间复杂度为 O(n)，但是空间复杂度为 O(n)

思路三：

在上面的图中可以看见，在有交点的情况下，无非就三种情况：由于在交点后(包括交点)的所有结点都相同

  • 链表 A 的长度 > 链表 B 的长度
  • 链表 A 的长度 = 链表 B 的长度
  • 链表 A 的长度 < 链表 B 的长度

如果我们能算出这个长度差，然后让长的那个链表先走这个长度差，再让两个链表一起走，直到走到相交点

举个例子，如下：

image-20201012093912222

  • 链表 A 长度 = 6；链表 B 长度 = 4；链表差 = 2
  • 让长度长的链表(A)先走链表差，即 pointerA 先走 2 个结点
  • pointerA 与 pointerB 一起遍历，直到遍历到相同结点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode a = headA;
    ListNode b = headB;

    // 链表A 和 链表B 的长度
    int la = 0, lb = 0;
    while (a.next != null) {
        la++;
        a = a.next;
    }
    while (b.next != null) {
        lb++;
        b = b.next;
    }

    // 此时说明直到 链表A 和 链表B 的最后一个结点都还没相交
    if (a != b) {
        return null;
    }

    // 链表A 的长度大于 链表B
    if (la > lb) {
        int sub = la - lb;
        while (sub > 0){
            headA = headA.next;
            sub--;
        }
    }
    // 链表A 的长度小于 链表B
    else {
        int sub = lb - la;
        while (sub > 0){
            headB = headB.next;
            sub--;
        }
    }

    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

另外一种简洁的写法，思路一样

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}
  • 如果没有重合部分，那么 a 和 b 在某一时间点 一定会同时走到 null，从而结束循环；
  • 如果有重合部分，分两种情况：
    • 长度相同的话， a 和 b 一定是同时到达相遇点，然后返回；
    • 长度不同的话，较短的链表先到达结尾，然后指针转向较长的链表。此刻，较长的链表继续向末尾走，多走的距离刚好就是最开始介绍的解法，链表的长度差，走完之后指针转向较短的链表。然后继续走的话，相遇的位置就刚好是相遇点了。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/10/12/0160-Intersection-of-Two-Linked-Lists/

更新于：2022年3月26日

Leetcode

Array

LinkedList

评论