LeetCode 160 Intersection of Two Linked Lists

    
        标签：
        
            链表问题
        
            LeetCode
        
    发布于：2022-02-05 17:40:13
    编辑于：2022-02-05 18:50:37
    浏览量：1026

题目分析

https://leetcode.com/problems/intersection-of-two-linked-lists/

直接法

两个链表分别遍历一遍，记录各自的长度，首先通过最终节点判断是否相交。

如果相交的话，算一下两个的长度之差，记为 n，重置两个指针为两个链表的开头处，让较长的那个先走 n 步，之后较短的那个也开始走，每走一步判断一下是否相同，第一个相同的节点即交点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto ap = headA;
        auto bp = headB;
        int a = 0;
        int b = 0;
        while (ap && ap->next != nullptr) {
            ap = ap->next;
            a++;
        }
        while (bp && bp->next != nullptr) {
            bp = bp->next;
            b++;
        }
        if (ap != bp) return nullptr;
        int n = a - b;
        auto fast = headA;
        auto slow = headB;
        if (n < 0) {
            n *= -1;
            fast = headB;
            slow = headA;
        }
        for(int i = 1; i <= n; i++) {
            fast = fast->next;
        }
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

拼接法

https://labuladong.gitee.io/algo/2/17/16/#两个链表是否相交

解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。

如下图所示，让 p1 和 p2 走完当前链表后走另一条链表，这样其必然在第一个公共部分相交，如果有的话。

实现上要注意 if (p1 == p2) break; 这一行，我们不能仅依赖 while 循环条件来判别，当 p1，p2 其中一个换链表后，我们应当在此时判断一下是否相同，对应的 case 为其中一个链表只有共享部分，而没有独有的部分。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p1 = headA;
        auto p2 = headB;
        auto b1 = true;
        auto b2 = true;
        while (p1 != p2) {
            if (p1 == nullptr && b1) {
                p1 = headB;
                b1 = false;
            }
            if (p2 == nullptr && b2) {
                p2 = headA;
                b2 = false;
            }
            
            if (p1 == p2) break; 
            
            p1 = p1->next;
            p2 = p2->next;
        }
        if (p1 == nullptr) return nullptr;
        return p1;
    }
};

实际上我们没有必要记录是否已经走到过链表结尾，因为 AB 和 BA 的最后都是 nullptr，此时循环必然结束。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p1 = headA;
        auto p2 = headB;
        while (p1 != p2) {
            if (p1) {
                p1 = p1->next;
            } else {
                p1 = headB;
            }
            
            if (p2) {
                p2 = p2->next;
            } else {
                p2 = headA;
            }
        }

        return p1;
    }
};

拼接成环法

如果把两条链表首尾相连，那么「寻找两条链表的交点」的问题转换成了前面讲的「寻找环起点」的问题

图片和思路同样来自于 https://labuladong.gitee.io/algo/2/17/16/#合并-k-个有序链表

Links: leetcode-160-intersection-of-two-linked-lists