C++實(shí)現(xiàn)LeetCode(160.求兩個鏈表的交點(diǎn))

更新時間：2021年07月30日 16:29:01 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(160.求兩個鏈表的交點(diǎn)),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 160.Intersection of Two Linked Lists 求兩個鏈表的交點(diǎn)

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
↘
c1 → c2 → c3
↗
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

我還以為以后在不能免費(fèi)做OJ的題了呢，想不到 OJ 又放出了不需要買書就能做的題，業(yè)界良心啊，哈哈^_^。這道求兩個鏈表的交點(diǎn)題要求執(zhí)行時間為 O(n)，則不能利用類似冒泡法原理去暴力查找相同點(diǎn)，事實(shí)證明如果鏈表很長的話，那樣的方法效率很低。我也想到會不會是像之前刪除重復(fù)元素的題一樣需要用兩個指針來遍歷，可是想了好久也沒想出來怎么弄。無奈上網(wǎng)搜大神們的解法，發(fā)覺其實(shí)解法很簡單，因?yàn)槿绻麅蓚€鏈長度相同的話，那么對應(yīng)的一個個比下去就能找到，所以只需要把長鏈表變短即可。具體算法為：分別遍歷兩個鏈表，得到分別對應(yīng)的長度。然后求長度的差值，把較長的那個鏈表向后移動這個差值的個數(shù)，然后一一比較即可。代碼如下：

C++ 解法一：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return NULL;
        int lenA = getLength(headA), lenB = getLength(headB);
        if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; ++i) headB = headB->next;
        } else {
            for (int i = 0; i < lenA - lenB; ++i) headA = headA->next;
        }
        while (headA && headB && headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }
        return (headA && headB) ? headA : NULL;
    }
    int getLength(ListNode* head) {
        int cnt = 0;
        while (head) {
            ++cnt;
            head = head->next;
        }
        return cnt;
    }
};

Java 解法一：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int lenA = getLength(headA), lenB = getLength(headB);
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; ++i) headA = headA.next;
        } else {
            for (int i = 0; i < lenB - lenA; ++i) headB = headB.next;
        }
        while (headA != null && headB != null && headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return (headA != null && headB != null) ? headA : null;
    }
    public int getLength(ListNode head) {
        int cnt = 0;
        while (head != null) {
            ++cnt;
            head = head.next;
        }
        return cnt;
    }
}

這道題還有一種特別巧妙的方法，雖然題目中強(qiáng)調(diào)了鏈表中不存在環(huán)，但是我們可以用環(huán)的思想來做，我們讓兩條鏈表分別從各自的開頭開始往后遍歷，當(dāng)其中一條遍歷到末尾時，我們跳到另一個條鏈表的開頭繼續(xù)遍歷。兩個指針最終會相等，而且只有兩種情況，一種情況是在交點(diǎn)處相遇，另一種情況是在各自的末尾的空節(jié)點(diǎn)處相等。為什么一定會相等呢，因?yàn)閮蓚€指針走過的路程相同，是兩個鏈表的長度之和，所以一定會相等。這個思路真的很巧妙，而且更重要的是代碼寫起來特別的簡潔，參見代碼如下：

C++ 解法二：

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;
    }
};

Java 解法二：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA, b = headB;
        while (a != b) {
            a = (a != null) ? a.next : headB;
            b = (b != null) ? b.next : headA;
        }
        return a;
    }
}

類似題目：

Minimum Index Sum of Two Lists

參考資料：

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

https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49792/Concise-JAVA-solution-O(1)-memory-O(n)-time

https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(160.求兩個鏈表的交點(diǎn))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)求兩個鏈表的交點(diǎn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: