【C++】LeetCode：LCR 023. 相交链表

题干

LCR 023. 相交链表

的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

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

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

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

题解：双指针法

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {};
};

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (!headA || !headB) return nullptr;

    ListNode *first = headA;
    ListNode *second = headB;

    while (first != second) {
        first = (first ? first->next : headB);
        second = (second ? second->next : headA);
    }

    return first;
}

解析：

数学解释

假设：

• 链表 A 的非相交部分长度为 lenA - lenC。
• 链表 B 的非相交部分长度为 lenB - lenC。

当两个指针重定向后，它们走过的总距离分别是：

• first 走过的总距离：(lenA - lenC) + lenC + (lenB - lenC) = lenA + lenB - lenC
• second 走过的总距离：(lenB - lenC) + lenC + (lenA - lenC) = lenB + lenA - lenC

由于 (lenA + lenB - lenC) 和 (lenB + lenA - lenC) 是相同的，所以两个指针最终会在相交节点处相遇。

其实，互相抵消掉重叠的lenc，各自走的长度就是lenA + lenB

个人理解：每次移动指针就算一个距离，双方移动的距离都是A+B，这个算法不是一定会在相交点结束，而是走的距离一样，一定都会在两个链表的最后一个节点停止。只不过，如果相交了，两个链的最后一个点都是相交点，如果没相交那就都是nullptr。我的说法忽略了重复节点的遍历，因为从数学的角度上可以直接互相抵消这段距离。

原文地址：https://blog.csdn.net/weixin_46506407/article/details/144034661

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！