資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目解答非常聰明的解法，因?yàn)閮蓚€(gè)的長(zhǎng)度不一樣，所以它讓兩個(gè)指針通過(guò)兩次循環(huán)，來(lái)把兩個(gè)都掃一遍。因?yàn)楣驳牟糠窒嗤?，所以?dāng)它們相遇的時(shí)候，就是。
題目：
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 {
//非常聰明的解法，因?yàn)閮蓚€(gè)linkedlist的長(zhǎng)度不一樣，所以它讓兩個(gè)指針通過(guò)兩次循環(huán)，
//來(lái)把兩個(gè)linkedlist都掃一遍。因?yàn)楣驳牟糠窒嗤?，所以?dāng)它們相遇的時(shí)候，就是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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64913.html
摘要：示例輸入輸出輸入解釋相交節(jié)點(diǎn)的值為注意，如果兩個(gè)列表相交則不能為。解釋這兩個(gè)鏈表不相交，因此返回。注意如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。此時(shí)將指向鏈表長(zhǎng)鏈表的頭節(jié)點(diǎn)，不變。 愛(ài)寫(xiě)B(tài)ug（ID：iCodeBugs） 編寫(xiě)一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。 Write a program to find the node at which the i...
摘要：示例輸入輸出輸入解釋相交節(jié)點(diǎn)的值為注意，如果兩個(gè)列表相交則不能為。解釋這兩個(gè)鏈表不相交，因此返回。注意如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。此時(shí)將指向鏈表長(zhǎng)鏈表的頭節(jié)點(diǎn)，不變。 愛(ài)寫(xiě)B(tài)ug（ID：iCodeBugs） 編寫(xiě)一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。 Write a program to find the node at which the i...
摘要：得到個(gè)鏈條的長(zhǎng)度。將長(zhǎng)的鏈條向前移動(dòng)差值兩個(gè)指針一起前進(jìn)，遇到相同的即是交點(diǎn)，如果沒(méi)找到，返回空間復(fù)雜度，時(shí)間復(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)計(jì)交點(diǎn)到終點(diǎn)的步數(shù)比較困難，我們可以直接統(tǒng)計(jì)從最短鏈表開(kāi)頭到交點(diǎn)的步數(shù)，其實(shí)是等價(jià)的。 雙指針?lè)?復(fù)雜度 時(shí)間 O(N) 空間 O(1) 思路 先算出兩個(gè)鏈表各自的長(zhǎng)度，然后從較長(zhǎng)的鏈表先遍歷，遍歷到較長(zhǎng)鏈表剩余長(zhǎng)度和較短鏈表一樣時(shí)，用兩個(gè)指針同時(shí)遍歷兩個(gè)鏈表。這樣如果鏈表有交點(diǎn)的話，兩個(gè)指針已經(jīng)一定會(huì)相遇。 代碼 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 ↘ ...
閱讀 1972·2021-10-25 09:48
閱讀 2800·2021-09-22 14:59
閱讀 1763·2019-08-29 16:52
閱讀 869·2019-08-29 16:07
閱讀 2310·2019-08-29 12:38
閱讀 1766·2019-08-26 13:23
閱讀 886·2019-08-26 11:49
閱讀 3282·2019-08-26 10:56
