LeetCode 160 Intersection of Two Linked Lists

Tag: 链表问题 LeetCode Posted on 2022-02-05 17:40:13 Edited on 2022-02-05 18:50:37 Views: 152

题目分析

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-个有序链表

未经允许,禁止转载,本文源站链接:https://iamazing.cn/