面试题02.07-链表相交

Doublew2w大约 4 分钟

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

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

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

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

示例 1：

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

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

  输入： 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
0 <= m, n <= 3 * 10 ⁴
1 <= Node.val <= 10 ⁵
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点， intersectVal 为 0
如果 listA 和 listB 有交点， intersectVal == listA [skipA + 1] == listB [skipB + 1]

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

前置知识

双指针
链表
哈希表

思路

相交部分长度为 c，listA 长度为 a，listb 长度为 b。

有两个变量 headA、headB 分别从 listA、listB 分别出发。

当 headA 走完 listA 时，从 headB 继续走。
当 headB 走完 listB 时，从 headA 继续走。
headA == headB 时就是相交节点
- headA 共走了 a+（b-c）
- headB 共走了 b+（a-c）
若两链表有公共尾部 (即 c > 0 ) ：指针 A, B 同时指向第一个相交节点。
若两链表无公共尾部 (即 c = 0 ) ：指针 A , B 同时指向 null 。

关键点

双指针遍历各自所在链表后，在遍历对方的链表，第一次「相等」就是相交点
「相等」有可能两个指针都指向 null

代码

语言支持：Java

Java Code:


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // A 链长度为 a
        // B 链长度为 b
        // A 和 B 重叠的链长度为 c
        // A 相交的位置在 a+b-c
        // B 相交的位置在 b+a-c
        ListNode first = headA;
        ListNode second = headB;
        while(first != second){ // 循环终止条件
            first = first == null? headB:first.next;
            second = second == null? headA:second.next;
        }
        return first;
    }
}

复杂度分析

令 a 为 listA 长度，b 为 listB 长度

时间复杂度： $O(a+b)$ ，最差情况下（即 $∣a−b∣=1$ , $c=0$ ），此时需遍历 $a+b$ 个节点。
空间复杂度： $O(1)$

面试题02.07-链表相交

题目地址(面试题 02.07. 链表相交 - 力扣（LeetCode）)

题目描述

前置知识

思路

关键点

代码