Leetcode 面试题 02.07. 链表相交（画图分析）

同：160.链表相交

力扣传送门(opens new window)

给你两个单链表的头节点 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 。

解题思路：

当解决两个链表是否相交的问题时，一个直观的思路是分别遍历两个链表，找到它们的尾节点，然后判断尾节点是否相同。如果相同，说明两个链表相交，否则不相交。

然而，上述的思路需要遍历两个链表，时间复杂度为O(m+n)，其中m和n分别是两个链表的长度。如果两个链表很长，这种解法可能会导致耗时较长。

优化的思路是通过双指针遍历两个链表，使得两个指针能够同时到达交点位置。具体步骤如下：

1. 创建两个指针p1和p2，分别指向两个链表的头结点headA和headB。
2. 在循环中，比较p1和p2指向的节点是否相同。如果相同，则说明找到了交点，直接返回该节点。
3. 如果p1指向的节点为null（即p1已经遍历完链表headA），则将其指向链表headB的头结点，以便继续遍历。
4. 如果p2指向的节点为null（即p2已经遍历完链表headB），则将其指向链表headA的头结点，以便继续遍历。
5. 重复步骤2-4，直到找到交点或者两个指针同时指向null（表示两个链表都没有交点），循环结束。

通过这种方法，可以保证两个指针p1和p2在遍历完各自的链表后同时到达交点位置，从而找到交点。这种解法的时间复杂度为O(m+n)，其中m和n分别是两个链表的长度，相较于直接遍历两个链表的解法，时间复杂度得到了优化。

代码实现：

java

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 创建指针p1，指向链表headA的头结点
        ListNode p1 = headA;  
        // 创建指针p2，指向链表headB的头结点
        ListNode p2 = headB;  
        // 当p1和p2指向的节点不相同时执行循环
        while (p1 != p2) {  
            // 如果p1已经到达链表headA的末尾，则将其指向链表headB的头结点，否则将p1指向下一个节点
            p1 = p1 == null ? headB : p1.next;  
            // 如果p2已经到达链表headB的末尾，则将其指向链表headA的头结点，否则将p2指向下一个节点
            p2 = p2 == null ? headA : p2.next;  
        }
        // 返回p1，此时p1和p2指向的节点相同，表示两个链表有交点
        return p1;  
    }
}

在循环中，当指针 p1 和 p2 都遍历完各自的链表后，最终会同时指向 null。此时循环结束，返回 p1（或 p2）即可，它们都指向 null，表示两个链表没有交点。

在没有交点的情况下，当 p1 遍历完链表 headA 后，会将其指向链表 headB 的头结点，而 p2 遍历完链表 headB 后，会将其指向链表 headA 的头结点。这样，它们会继续遍历对方的链表，直到最终同时指向 null。

因此，即使两个链表没有交点，双指针遍历的过程中也能够正确地判断出它们不相交，并返回 null 作为结果。

python

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # 创建指针p1，指向链表headA的头结点
        p1 = headA
        # 创建指针p2，指向链表headB的头结点
        p2 = headB
        # 当p1和p2指向的节点不相同时执行循环
        while p1 != p2:
            # 如果p1已经到达链表headA的末尾，则将其指向链表headB的头结点，否则将p1指向下一个节点
            p1 = headB if p1 is None else p1.next
            # 如果p2已经到达链表headB的末尾，则将其指向链表headA的头结点，否则将p2指向下一个节点
            p2 = headA if p2 is None else p2.next
        # 返回p1，此时p1和p2指向的节点相同，表示两个链表有交点
        return p1

c++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 创建指针p1，指向链表headA的头结点
        ListNode *p1 = headA;
        // 创建指针p2，指向链表headB的头结点
        ListNode *p2 = headB;
        // 当p1和p2指向的节点不相同时执行循环
        while (p1 != p2) {
            // 如果p1已经到达链表headA的末尾，则将其指向链表headB的头结点，否则将p1指向下一个节点
            p1 = p1 == nullptr ? headB : p1->next;
            // 如果p2已经到达链表headB的末尾，则将其指向链表headA的头结点，否则将p2指向下一个节点
            p2 = p2 == nullptr ? headA : p2->next;
        }
        // 返回p1，此时p1和p2指向的节点相同，表示两个链表有交点
        return p1;
    }
};