160. Intersection of Two Linked Lists

molyzzx 發布于2019-08-14 14:16 / 2876人閱讀

摘要：題目解答非常聰明的解法，因為兩個的長度不一樣，所以它讓兩個指針通過兩次循環，來把兩個都掃一遍。因為公共的部分相同，所以當它們相遇的時候，就是。

題目：
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.

解答：

public class Solution {
    //非常聰明的解法，因為兩個linkedlist的長度不一樣，所以它讓兩個指針通過兩次循環，
    //來把兩個linkedlist都掃一遍。因為公共的部分相同，所以當它們相遇的時候，就是intersection。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        
        ListNode a = headA;
        ListNode b = headB;
        
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        
        return a;
    }
}

云服務器 GPU云服務器 Intersection Lists linked two

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64913.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] Intersection of Two Linked Lists 鏈表交點

摘要：但是統計交點到終點的步數比較困難，我們可以直接統計從最短鏈表開頭到交點的步數，其實是等價的。雙指針法復雜度時間 O(N) 空間 O(1) 思路先算出兩個鏈表各自的長度，然后從較長的鏈表先遍歷，遍歷到較長鏈表剩余長度和較短鏈表一樣時，用兩個指針同時遍歷兩個鏈表。這樣如果鏈表有交點的話，兩個指針已經一定會相遇。代碼 public class Solution { publ...

andycall 2019-08-14 12:29 評論0 收藏0
[LintCode/LeetCode] Intersection of Two Linked Lis

Problem Write a program to find the node at which the intersection of two singly linked lists begins. Example The following two linked lists: A: a1 → a2 ↘ ...

OldPanda 2019-08-14 15:19 評論0 收藏0