LeetCode: 160. 相交链表

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

160. 相交链表

LeetCode - 160. 相交链表

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

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

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

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

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

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

示例 3：

输入：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 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 10⁴
1 <= Node.val <= 10⁵
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

思路分析

没想到竟然可以将两个链表"相加"就可以得出正确结果：两个"相加"，正好两个长度相等，最后部分就是重叠部分，双指针完美搞定！

链表 x+z 和 y+z，两个链表拼接，则是 (x+z+y)+z 和 (y+z+x)+z，就可以通过相同的步数找到最后的共同部分 z。

一刷
二刷
三刷
四刷

 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
47
/**
 * Runtime: 1 ms, faster than 99.29% of Java online submissions for Intersection of Two Linked Lists.
 *
 * Memory Usage: 43.3 MB, less than 5.71% of Java online submissions for Intersection of Two Linked Lists.
 *
 * Copy from: https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len![Java solution without knowing the difference in len! - LeetCode Discuss]
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-12 11:12
 */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (Objects.isNull(headA) || Objects.isNull(headB)) {
        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;
}

/**
 * Runtime: 8 ms, faster than 14.19% of Java online submissions for Intersection of Two Linked Lists.
 * <p>
 * Memory Usage: 44.2 MB, less than 5.71% of Java online submissions for Intersection of Two Linked Lists.
 */
public ListNode getIntersectionNodeSet(ListNode headA, ListNode headB) {
    if (Objects.isNull(headA) || Objects.isNull(headB)) {
        return null;
    }
    Set<ListNode> nodes = new HashSet<>();
    ListNode current = headA;
    while (Objects.nonNull(current)) {
        nodes.add(current);
        current = current.next;
    }
    current = headB;
    while (Objects.nonNull(current)) {
        if (nodes.contains(current)) {
            return current;
        }
        current = current.next;
    }
    return null;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * 两个链表逻辑拼接
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-07-02 21:37:57
 */
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-07-02 21:37:57
 */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  ListNode a = headA;
  ListNode b = headB;
  while (a != b) {
    if (a == null) {
      a = headB;
    } else {
      a = a.next;
    }
    if (b == null) {
      b = headA;
    } else {
      b = b.next;
    }
  }
  return a;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-10-30 21:33:00
 */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  ListNode ha = headA, hb = headB;
  while (ha != hb) { // 如果不相交，则最后都会走到 null，也会退出循环
    ha = ha == null ? headB : ha.next;
    hb = hb == null ? headA : hb.next;
  }
  return ha;
}

LeetCode: 160. 相交链表

友情支持

160. 相交链表

思路分析

参考资料