160 相交链表

一、题目

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

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

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

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

自定义评测：

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

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

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

二、题解

思路： 双指针走「拼接路径」。

  • 指针 pA 从 headA 出发，走到尽头后转到 headB；指针 pB 从 headB 出发，走到尽头后转到 headA。
  • 这样两个指针走过的总长度相同（都是 lenA + lenB），若链表相交则会在交点相遇；若不相交则同时变为 null 退出循环。
  • 最终返回 pA 即为相交起始节点（或 null）。
/**
 * 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) {
        // 定义两个小人 pA 和 pB，分别站在两个链表的起点
        ListNode pA = headA, pB = headB;

        // 【边界】如果其中一个链表根本不存在，那就绝对不可能相交
        if(headA == null || headB == null) return null;

        // 【核心循环】只要两个小人还没相遇（没有站在同一个节点上），就继续走
        while(pA != pB) {

            // 重点理解部分！！！
            // pA 在链表 A 上走。如果它走到了 A 的尽头 (pA == null)，
            // 它就“瞬移”去走链表 B (变成 headB)。否则继续走 A 的下一步。
            pA = pA == null ? headB : pA.next;

            // pB 同理。走完了自己这边的链表 B，就“跨界”去走链表 A。
            pB = pB == null ? headA : pB.next;
        }

        // 最终两人相遇。要么是在相交节点相遇，要么是根本没相交，两人同时走到了尽头（都变成了 null）。
        return pA;
    }
}

时间复杂度：O(n+m)O(n + m)

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

评论