資訊專欄INFORMATION COLUMN
摘要：但是統(tǒng)計(jì)交點(diǎn)到終點(diǎn)的步數(shù)比較困難，我們可以直接統(tǒng)計(jì)從最短鏈表開頭到交點(diǎn)的步數(shù)，其實(shí)是等價(jià)的。
雙指針法 復(fù)雜度
時(shí)間 O(N) 空間 O(1)
思路先算出兩個(gè)鏈表各自的長度，然后從較長的鏈表先遍歷，遍歷到較長鏈表剩余長度和較短鏈表一樣時(shí)，用兩個(gè)指針同時(shí)遍歷兩個(gè)鏈表。這樣如果鏈表有交點(diǎn)的話，兩個(gè)指針已經(jīng)一定會相遇。
代碼public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode nodea = headA, nodeb = headB;
int lena = 0, lenb = 0;
// 計(jì)算鏈表A的長度
while(nodea != null){
lena++;
nodea = nodea.next;
}
// 計(jì)算鏈表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;
}
}
后續(xù) Follow Up
Q：如果是K個(gè)鏈表的交點(diǎn)如何求？
A：先找出K個(gè)鏈表中長度最短的那個(gè)，然后用同樣的方法將其他鏈表和這個(gè)鏈表兩兩比較，因?yàn)槊總€(gè)都有可能有一個(gè)不同的交點(diǎn)，所以我們要維護(hù)一個(gè)全局最優(yōu)的交點(diǎn)，更新這個(gè)全局最優(yōu)交點(diǎn)的條件，是這個(gè)交點(diǎn)到終點(diǎn)的步數(shù)是最少的。但是統(tǒng)計(jì)交點(diǎn)到終點(diǎn)的步數(shù)比較困難，我們可以直接統(tǒng)計(jì)從最短鏈表開頭到交點(diǎn)的步數(shù)，其實(shí)是等價(jià)的。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64504.html
摘要：示例輸入輸出輸入解釋相交節(jié)點(diǎn)的值為注意，如果兩個(gè)列表相交則不能為。解釋這兩個(gè)鏈表不相交，因此返回。注意如果兩個(gè)鏈表沒有交點(diǎn)，返回在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。此時(shí)將指向鏈表長鏈表的頭節(jié)點(diǎn)，不變。 愛寫B(tài)ug（ID：iCodeBugs） 編寫一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。 Write a program to find the node at which the i...
摘要：示例輸入輸出輸入解釋相交節(jié)點(diǎn)的值為注意，如果兩個(gè)列表相交則不能為。解釋這兩個(gè)鏈表不相交，因此返回。注意如果兩個(gè)鏈表沒有交點(diǎn)，返回在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。此時(shí)將指向鏈表長鏈表的頭節(jié)點(diǎn)，不變。 愛寫B(tài)ug（ID：iCodeBugs） 編寫一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。 Write a program to find the node at which the i...
摘要：得到個(gè)鏈條的長度。將長的鏈條向前移動(dòng)差值兩個(gè)指針一起前進(jìn)，遇到相同的即是交點(diǎn)，如果沒找到，返回空間復(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...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：還是鏈表算法題目描述給出兩個(gè)無環(huán)單鏈表判斷和是否相交。所以可以得出另外一種解法，先遍歷鏈表，記住尾節(jié)點(diǎn)，然后遍歷鏈表，比較兩個(gè)鏈表的尾節(jié)點(diǎn)，如果相同則相交，不同則不相交。想法還是奇妙的。算法寫起來不難，難的是想到這個(gè)。 還是鏈表算法 題目描述：給出兩個(gè)無環(huán)單鏈表A: a1 → a2 ↘ c1 → c2 → c3 → ...
閱讀 1217·2021-09-03 10:44
閱讀 617·2019-08-30 13:13
閱讀 2808·2019-08-30 13:11
閱讀 1976·2019-08-30 12:59
閱讀 1043·2019-08-29 15:32
閱讀 1608·2019-08-29 15:25
閱讀 1003·2019-08-29 12:24
閱讀 1290·2019-08-27 10:58
