相交链表

发表于 | 分类于 |
字数统计: 776 字 | 阅读时长 ≈ 3 分钟

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

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

img

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

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

示例 1：img
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0)。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：img
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0)。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：img
输入：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 。

方法一：双指针

如果两个链表相交，那么相交点之后的长度是相同的

我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。

为此，我们必须消除两个链表的长度差

  • 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
  • 如果 pA 到了末尾，则 pA = headB 继续遍历
  • 如果 pB 到了末尾，则 pB = headA 继续遍历
  • 比较长的链表指针指向较短链表head时，长度差就消除了
  • 如此，只需要将最短链表遍历两次即可找到位置

相交链表.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null) return null;
    ListNode A = headA, B = headB;
    while(A != B) {
      A = A == null ? headB : A.next;
      B = B == null ? headA : B.next;
    }
    return A;
  }
}

var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB) return null
    let A = headA, B = headB
    while(A !== B) {
        A = A == null ? headB : A.next
        B = B == null ? headA : B.next
    }
    return A
};

复杂度分析

  • 时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次

  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：41.4 MB, 在所有 Java 提交中击败了26.14%的用户