30 Day Challenge Day 6 | Leetcode 160. Intersection of Two Linked Lists

题解

方法一:龟兔赛跑

最先想到的方法,姑且叫它“龟兔赛跑”:先计算两条LinkedList的长度,然后让长的那条先走,直到剩下的节点数一样,相当于回到同一起跑线。接下来,以同样的步调向后遍历并比较节点。代码写起来不是很简洁,但是并不影响复杂度,能通过。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0, lenB = 0;

        ListNode* node = headA;
        while (node) {
            node = node->next;
            lenA++;
        }

        node = headB;
        while (node) {
            node = node->next;
            lenB++;
        }

        if (lenA >= lenB) {
            while (lenA > lenB) {
                headA = headA->next;
                lenA--;
            }
            while (headA && headB && headA != headB) {
                headA = headA->next;
                headB = headB->next;
            }
            return headA;
        }
        else {
            while (lenB > lenA) {
                headB = headB->next;
                lenB--;
            }
            while (headA && headB && headA != headB) {
                headA = headA->next;
                headB = headB->next;
            }
            return headA;
        }        
    }
};

方法二:首尾相接制造环

对于两条不同长度的链表,可以进行首尾相接,制造一个环,这样,新的链表长度一样,可以省去上面方法中需要计算长度的步骤。也就是说,链表1的尾部与链表2的首部相接,再把链表2的尾部接回链表1的首部;另一边反之,从链表2的尾部接到链表1的首部,再接回链表2的首部,得到另一条新的链表。

下面的代码是参考别人的代码,已经非常简洁。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return NULL;
        ListNode *a = headA, *b = headB;
        while (a != b) {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        return a;
    }
};
上一篇:链表相交 三种思路 C++ 代码


下一篇:力扣 160 相交链表 快慢指针 双指针