相交链表

LeetCode 160.相交链表

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

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

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

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

方法1：双指针

算法思路：

设A的长度为a + c，B的长度为b + c，其中c 为尾部公共部分长度，可知 a + c + b = b + c + a。

当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

如果不存在交点，那么 a + b = b + a，以下实现代码中 l1 和 l2 会同时为 null，从而退出循环。

代码实现：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode l1 = headA, l2 = headB;
    while (l1 != l2) {
        l1 = (l1 == null) ? headB : l1.next;
        l2 = (l2 == null) ? headA : l2.next;
    }
    return l1;
}

复杂度分析：

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

  • 空间复杂度：O(1)O(1)。

参考

160. 相交链表 - 力扣（LeetCode）

Leetcode 题解 - 链表 | CS-Notes