<strike id="g6qsc"></strike>

<ul id="g6qsc"></ul>

[Leetcode] Intersection of Two Linked Lists 鏈表交點

andycall 發布于2019-08-14 12:29 / 1501人閱讀

摘要：但是統計交點到終點的步數比較困難，我們可以直接統計從最短鏈表開頭到交點的步數，其實是等價的。

雙指針法 復雜度

時間 O(N) 空間 O(1)

思路

先算出兩個鏈表各自的長度，然后從較長的鏈表先遍歷，遍歷到較長鏈表剩余長度和較短鏈表一樣時，用兩個指針同時遍歷兩個鏈表。這樣如果鏈表有交點的話，兩個指針已經一定會相遇。

代碼

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodea = headA, nodeb = headB;
        int lena = 0, lenb = 0;
        // 計算鏈表A的長度
        while(nodea != null){
            lena++;
            nodea = nodea.next;
        }
        // 計算鏈表B的長度
        while(nodeb != null){
            lenb++;
            nodeb = nodeb.next;
        }
        // 讓較長的鏈表先飛一會
        for(int i = 0; i < Math.abs(lena - lenb); i++){
            if(lenb > lena) headB = headB.next;
            else if(lena > lenb) headA = headA.next;
        }
        while(headA != null && headB != null){
            if(headA == headB) return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

后續 Follow Up

Q：如果是K個鏈表的交點如何求？
A：先找出K個鏈表中長度最短的那個，然后用同樣的方法將其他鏈表和這個鏈表兩兩比較，因為每個都有可能有一個不同的交點，所以我們要維護一個全局最優的交點，更新這個全局最優交點的條件，是這個交點到終點的步數是最少的。但是統計交點到終點的步數比較困難，我們可以直接統計從最短鏈表開頭到交點的步數，其實是等價的。

GPU云服務器云服務器 Intersection Lists linked 直線交點

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64504.html

LeetCode 160：相交鏈表 Intersection of Two Linked List

摘要：示例輸入輸出輸入解釋相交節點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結果后，兩個鏈表仍須保持原有的結構。此時將指向鏈表長鏈表的頭節點，不變。愛寫Bug（ID：iCodeBugs）編寫一個程序，找到兩個單鏈表相交的起始節點。 Write a program to find the node at which the i...

wing324 2019-08-16 18:38 評論0 收藏0
LeetCode 160：相交鏈表 Intersection of Two Linked List

摘要：示例輸入輸出輸入解釋相交節點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結果后，兩個鏈表仍須保持原有的結構。此時將指向鏈表長鏈表的頭節點，不變。愛寫Bug（ID：iCodeBugs）編寫一個程序，找到兩個單鏈表相交的起始節點。 Write a program to find the node at which the i...

ormsf 2019-07-31 11:29 評論0 收藏0
Intersection of 2 lists

摘要：得到個鏈條的長度。將長的鏈條向前移動差值兩個指針一起前進，遇到相同的即是交點，如果沒找到，返回空間復雜度，時間復雜度 Intersection of Two Linked ListsWrite a program to find the node at which the intersection of two singly linked lists begins. For examp...

thursday 2019-08-14 17:10 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
JAVASCRIPT算法（6）

摘要：還是鏈表算法題目描述給出兩個無環單鏈表判斷和是否相交。所以可以得出另外一種解法，先遍歷鏈表，記住尾節點，然后遍歷鏈表，比較兩個鏈表的尾節點，如果相同則相交，不同則不相交。想法還是奇妙的。算法寫起來不難，難的是想到這個。還是鏈表算法題目描述：給出兩個無環單鏈表A: a1 → a2 ↘ c1 → c2 → c3 → ...

FreeZinG 2019-08-21 17:56 評論0 收藏0