160. 相交链表

题目描述

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

注意：

• 整个链表结构中不存在环。
• 返回的节点需要是两个链表实际相交的节点，而不是一个新的节点。
• 不可以破坏链表的原始结构。

---

示例

示例 1：

输入：headA = [4,1,8,4,5], headB = [5,0,1,8,4,5]
输出：Intersected at '8'

示例 2：

输入：headA = [1,9,1,2,4], headB = [3,2,4]
输出：Intersected at '2'

示例 3：

输入：headA = [2,6,4], headB = [1,5]
输出：null
解释：两个链表不相交。

---

解题思路

为了在 O(n + m) 时间内完成相交节点的查找，同时保证不使用额外的空间，我们可以使用双指针法。

双指针法

1. 使用两个指针 pA 和 pB，分别指向两个链表的头部 headA 和 headB。
2. 两个指针以相同的速度遍历链表。如果指针到达链表的末尾，则将其切换到另一个链表的头部。
3. 如果两个链表相交，那么两个指针最终会在相交节点相遇。
4. 如果两个链表不相交，则两个指针会同时到达链表的尾部（null），退出循环。

为什么双指针可以找到相交节点？

• 当两个指针切换链表时，它们走过的路径长度相同：
  • 第一个指针：headA -> tailA -> headB -> tailB
  • 第二个指针：headB -> tailB -> headA -> tailA
• 如果两个链表相交，那么它们最后一定会在相交节点相遇。
• 如果两个链表不相交，那么两个指针最终会同时到达 null。

时间和空间复杂度

• 时间复杂度：O(n + m)，其中 n 和 m 分别是两个链表的长度。
• 空间复杂度：O(1)，只使用了两个额外的指针。

---

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取第一个链表
        String[] listAValues = scanner.nextLine().split(" ");
        ListNode headA = null;
        ListNode tailA = null;
        for (String val : listAValues) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (headA == null) {
                    headA = newNode;
                    tailA = newNode;
                } else {
                    tailA.next = newNode;
                    tailA = newNode;
                }
            }
        }

        // 读取第二个链表
        String[] listBValues = scanner.nextLine().split(" ");
        ListNode headB = null;
        ListNode tailB = null;
        for (String val : listBValues) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (headB == null) {
                    headB = newNode;
                    tailB = newNode;
                } else {
                    tailB.next = newNode;
                    tailB = newNode;
                }
            }
        }

        // 读取相交位置（如果有）
        int intersectPos = scanner.nextInt();

        // 创建相交链表
        if (intersectPos >= 0) {
            ListNode currentA = headA;
            ListNode currentB = headB;
            ListNode intersectNode = null;

            // 找到链表A的相交节点
            for (int i = 0; currentA != null && i < intersectPos; i++) {
                currentA = currentA.next;
            }

            // 让链表B的尾部连接到链表A的相交节点
            if (currentA != null) {
                intersectNode = currentA;
                while (currentB.next != null) {
                    currentB = currentB.next;
                }
                currentB.next = intersectNode;
            }
        }

        Solution solution = new Solution();
        ListNode result = solution.getIntersectionNode(headA, headB);

        if (result != null) {
            System.out.println("Intersected at '" + result.val + "'");
        } else {
            System.out.println("No intersection");
        }

        scanner.close();
    }
}

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // 初始化两个指针
        ListNode pA = headA;
        ListNode pB = headB;

        // 两个指针遍历链表
        while (pA != pB) {
            // 如果 pA 到达末尾，则切换到 headB，否则继续向下移动
            pA = (pA == null) ? headB : pA.next;

            // 如果 pB 到达末尾，则切换到 headA，否则继续向下移动
            pB = (pB == null) ? headA : pB.next;
        }

        // 如果相交，则 pA 和 pB 会在相交点相遇；否则会在 null 处相遇
        return pA;
    }
}

// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

---

测试用例

1. 相交链表：

   • 输入：headA = [4,1,8,4,5], headB = [5,0,1,8,4,5]
   • 输出：Intersected at '8'

2. 不相交链表：

   • 输入：headA = [2,6,4], headB = [1,5]
   • 输出：null

3. 一个链表为空：

   • 输入：headA = [], headB = [1,2,3]
   • 输出：null

4. 完全相同的链表：

   • 输入：headA = [1,2,3], headB = [1,2,3]
   • 输出：Intersected at '1'

---

注意事项

1. 链表长度差异：

   • 双指针法自动处理链表长度差异，因为指针切换链表后总会走相同的路径长度。

2. 空链表：

   • 如果任意一个链表为空，直接返回 null。

3. 原地操作：

   • 代码中仅使用两个指针操作链表，没有改变链表的结构，满足题目要求。

---

后续优化建议

a. 增加更多边界测试，例如一个链表为空或只有一个节点的情况。

b. 如果允许使用额外空间，可以用哈希表存储一个链表的节点，提高理解直观性，代价是空间复杂度增加到 (O(n))。