160. 相交链表

问题描述

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

注意：

• 返回结果后，链表必须保持其原始结构。

提示

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 30,000
• 1 <= Node.val <= 100,000
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶

设计一个时间复杂度为 O(m + n) 且仅用 O(1) 内存的解决方案。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
#include 
struct ListNode {
    int val;
    struct ListNode *next;
};
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* dummyA = headA;
    struct ListNode* dummyB = headB;
    while (dummyA != NULL)
    {
        while (dummyB != NULL)
        {
            if(dummyA == dummyB)
            {
                return dummyB;
            }
            if(dummyB->next != NULL)
            {
                dummyB = dummyB->next;
            }
            else
            {
                dummyB = headB;
                break;
            }
        }
        if(dummyA->next != NULL)
        {
            dummyA = dummyA->next;
        }
        else
        {
            dummyA = NULL;
        }
    }
    return NULL;
}

代码思路分析

该代码试图通过嵌套循环遍历两个链表，找到它们的相交节点。如果找到了相交节点，则返回该节点；如果没有找到，则返回 NULL。

分块拆解分析

定义结构和初始化

#include 
struct ListNode {
    int val;
    struct ListNode *next;
};

• 定义了一个单链表节点的结构体 ListNode，包含一个整数值 val 和一个指向下一个节点的指针 next。

核心函数 getIntersectionNode

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* dummyA = headA;
    struct ListNode* dummyB = headB;

• 初始化两个指针 dummyA 和 dummyB，分别指向链表 headA 和 headB 的头节点。

外层循环遍历 dummyA

    while (dummyA != NULL)
    {

• 遍历链表 headA，直到 dummyA 变为 NULL。

内层循环遍历 dummyB

        while (dummyB != NULL)
        {

• 遍历链表 headB，直到 dummyB 变为 NULL。

检查相交节点

            if(dummyA == dummyB)
            {
                return dummyB;
            }

• 如果 dummyA 和 dummyB 指向同一个节点，则返回该节点，即找到了相交点。

移动 dummyB 指针

            if(dummyB->next != NULL)
            {
                dummyB = dummyB->next;
            }
            else
            {
                dummyB = headB;
                break;
            }

• 如果 dummyB 的下一个节点不为 NULL，则移动到下一个节点。
• 如果 dummyB 的下一个节点为 NULL，则重置 dummyB 指针为 headB，并跳出内层循环。

移动 dummyA 指针

        if(dummyA->next != NULL)
        {
            dummyA = dummyA->next;
        }
        else
        {
            dummyA = NULL;
        }
    }
    return NULL;
}

• 如果 dummyA 的下一个节点不为 NULL，则移动到下一个节点。
• 如果 dummyA 的下一个节点为 NULL，则将 dummyA 置为 NULL，结束外层循环。
• 如果两个链表没有相交节点，则返回 NULL。

复杂度分析

时间复杂度

• 最坏情况下，外层循环遍历 headA 的每个节点，内层循环遍历 headB 的每个节点。因此时间复杂度为 O(m * n)，其中 m 和 n 分别是链表 headA 和 headB 的长度。

空间复杂度

• 该算法只使用了常数级的额外空间，因此空间复杂度为 O(1)。

改进

上述代码的时间复杂度较高，可以通过双指针法优化，将时间复杂度降低到 O(m + n)。具体思路是：

1. 初始化两个指针 pA 和 pB，分别指向 headA 和 headB。
2. 遍历两个链表，当 pA 到达末尾时，重置为 headB；当 pB 到达末尾时，重置为 headA。
3. 两个指针最终会相遇于相交节点，或同时到达链表末尾（无相交节点）。

优化后的代码实现

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }

    struct ListNode *pA = headA;
    struct ListNode *pB = headB;

    while (pA != pB) {
        pA = (pA == NULL) ? headB : pA->next;
        pB = (pB == NULL) ? headA : pB->next;
    }

    return pA;
}

会相交的原因

双指针法能够找到链表相交的节点，尽管两个链表的前置节点步长不一样，这是由于指针在遍历完一个链表后切换到另一个链表，从而消除了长度差异，使两个指针最终同步到达相交节点。以下是详细解释：

详细解释

假设链表 headA 的长度为 m，链表 headB 的长度为 n。为了简化说明，假设 headA 和 headB 在节点 C 相交。

• 链表 headA：A1 -> A2 -> ... -> Am -> C -> ...
• 链表 headB：B1 -> B2 -> ... -> Bn -> C -> ...

如果 m 和 n 不相等，那么指针 pA 和 pB 在初始遍历时到达末尾的时间不同。但通过交替切换遍历，两个指针在相同的时间步到达相交节点。下面是具体过程：

1. 初始化两个指针 pA 和 pB，分别指向 headA 和 headB。
2. 让两个指针分别遍历各自的链表。
3. 当指针到达链表末尾时，切换到另一个链表的头部继续遍历。
4. 最终，两个指针会在相交节点相遇，或者同时到达链表末尾（无相交节点）。

双指针遍历过程

pA的轨迹

• pA 从 headA 开始，走 m + 1 + c_to_end 步到达末尾，然后切换到 headB。
• pA 继续遍历 headB，走 n 步到达C。

pB的轨迹

• pB 从 headB 开始，走 n + 1 + c_to_end 步到达末尾，然后切换到 headA。
• pB 继续遍历 headA，走 m 步到达C。

由于 pA 和 pB 走的总步数相等（都是 m + n + 1 + c_to_end 步），如果m == n，则在第一次遍历的时候就会相遇在C的位置，否则在遍历完两个链表的节点后，两个指针会相遇于相交节点 C，或者同时到达链表末尾（无相交节点）。

时间复杂度和空间复杂度

• 时间复杂度：O(m + n)，因为每个指针最多遍历两个链表的总长度。
• 空间复杂度：O(1)，只使用了常数级的额外空间。

这种方法通过交替遍历链表，实现了在相同的时间步内找到两个链表的相交节点或确认无相交节点，避免了嵌套循环的高时间复杂度。

结果

源代码结果如下：

优化后结果如下：