資訊專欄INFORMATION COLUMN
摘要：題目解答非常聰明的解法，因為兩個的長度不一樣，所以它讓兩個指針通過兩次循環(huán)，來把兩個都掃一遍。因為公共的部分相同，所以當(dāng)它們相遇的時候，就是。
題目：
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的長度不一樣，所以它讓兩個指針通過兩次循環(huán)，
//來把兩個linkedlist都掃一遍。因為公共的部分相同，所以當(dāng)它們相遇的時候，就是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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/64913.html
摘要：示例輸入輸出輸入解釋相交節(jié)點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結(jié)果后，兩個鏈表仍須保持原有的結(jié)構(gòu)。此時將指向鏈表長鏈表的頭節(jié)點，不變。 愛寫B(tài)ug（ID：iCodeBugs） 編寫一個程序，找到兩個單鏈表相交的起始節(jié)點。 Write a program to find the node at which the i...
摘要：示例輸入輸出輸入解釋相交節(jié)點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結(jié)果后，兩個鏈表仍須保持原有的結(jié)構(gòu)。此時將指向鏈表長鏈表的頭節(jié)點，不變。 愛寫B(tài)ug（ID：iCodeBugs） 編寫一個程序，找到兩個單鏈表相交的起始節(jié)點。 Write a program to find the node at which the i...
摘要：得到個鏈條的長度。將長的鏈條向前移動差值兩個指針一起前進，遇到相同的即是交點，如果沒找到，返回空間復(fù)雜度，時間復(fù)雜度 Intersection of Two Linked ListsWrite a program to find the node at which the intersection of two singly linked lists begins. For examp...
摘要：但是統(tǒng)計交點到終點的步數(shù)比較困難，我們可以直接統(tǒng)計從最短鏈表開頭到交點的步數(shù)，其實是等價的。 雙指針法 復(fù)雜度 時間 O(N) 空間 O(1) 思路 先算出兩個鏈表各自的長度，然后從較長的鏈表先遍歷，遍歷到較長鏈表剩余長度和較短鏈表一樣時，用兩個指針同時遍歷兩個鏈表。這樣如果鏈表有交點的話，兩個指針已經(jīng)一定會相遇。 代碼 public class Solution { publ...
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 ↘ ...
閱讀 2023·2021-10-25 09:48
閱讀 2893·2021-09-22 14:59
閱讀 1819·2019-08-29 16:52
閱讀 934·2019-08-29 16:07
閱讀 2381·2019-08-29 12:38
閱讀 1848·2019-08-26 13:23
閱讀 939·2019-08-26 11:49
閱讀 3352·2019-08-26 10:56
