快捷導(dǎo)航

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

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

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

[LeetCode] 160.Intersection of Two Linked Lists 求兩個(gè)鏈表的交點(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è)界良心啊，哈哈^_^。這道求兩個(gè)鏈表的交點(diǎn)題要求執(zhí)行時(shí)間為 O(n)，則不能利用類似冒泡法原理去暴力查找相同點(diǎn)，事實(shí)證明如果鏈表很長的話，那樣的方法效率很低。我也想到會(huì)不會(huì)是像之前刪除重復(fù)元素的題一樣需要用兩個(gè)指針來遍歷，可是想了好久也沒想出來怎么弄。無奈上網(wǎng)搜大神們的解法，發(fā)覺其實(shí)解法很簡單，因?yàn)槿绻麅蓚€(gè)鏈長度相同的話，那么對(duì)應(yīng)的一個(gè)個(gè)比下去就能找到，所以只需要把長鏈表變短即可。具體算法為：分別遍歷兩個(gè)鏈表，得到分別對(duì)應(yīng)的長度。然后求長度的差值，把較長的那個(gè)鏈表向后移動(dòng)這個(gè)差值的個(gè)數(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)其中一條遍歷到末尾時(shí)，我們跳到另一個(gè)條鏈表的開頭繼續(xù)遍歷。兩個(gè)指針最終會(huì)相等，而且只有兩種情況，一種情況是在交點(diǎn)處相遇，另一種情況是在各自的末尾的空節(jié)點(diǎn)處相等。為什么一定會(huì)相等呢，因?yàn)閮蓚€(gè)指針走過的路程相同，是兩個(gè)鏈表的長度之和，所以一定會(huì)相等。這個(gè)思路真的很巧妙，而且更重要的是代碼寫起來特別的簡潔，參見代碼如下：

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.求兩個(gè)鏈表的交點(diǎn))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)求兩個(gè)鏈表的交點(diǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: