資訊專欄INFORMATION COLUMN
摘要：示例輸入輸出輸入解釋相交節點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結果后，兩個鏈表仍須保持原有的結構。此時將指向鏈表長鏈表的頭節點，不變。
愛寫Bug（ID：iCodeBugs）
編寫一個程序，找到兩個單鏈表相交的起始節點。
Write a program to find the node at which the intersection of two singly linked lists begins.
如下面的兩個鏈表：
在節點 c1 開始相交。
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 輸出：Reference of the node with value = 8 輸入解釋：相交節點的值為 8 （注意，如果兩個列表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
示例 2：**
輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 輸出：Reference of the node with value = 2 輸入解釋：相交節點的值為 2 （注意，如果兩個列表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。
示例 3：**
輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 輸出：null 輸入解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。 解釋：這兩個鏈表不相交，因此返回 null。
注意：
如果兩個鏈表沒有交點，返回 null.
在返回結果后，兩個鏈表仍須保持原有的結構。
可假定整個鏈表結構中沒有循環。
程序盡量滿足 O(_n_) 時間復雜度，且僅用 O(_1_) 內存。 相交鏈表
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.
解題思路：注意：長鏈表比短鏈表多出的長度是無需比較的
剛開始我是想著直接從兩個鏈表末尾向前遍歷對比節點是否相等，后面才看到是單鏈表。但是依然有很多的解題方法：
哈希表：把一個鏈表的節點先存儲在哈希表，遍歷另一個節點并判斷該節點地址是否在哈希表中出現過如果出現過，輸出該節點。需要占用額外空間 O(n)。
如果按要求在 O(1) 空間復雜度解題，最容易想到的就是：遍歷鏈表得到鏈表長度，計算雙鏈表差值，長鏈表減去差值得到的剩下的鏈表與短鏈表長度相等，然后開始比較地址。，當遇到第一個節點地址相同時即為所求。
這個原理簡單，但是代碼太冗長了，我們來看另一種更優雅的解法，看圖幫助理解：
定義兩個指針curA、curB分別從鏈表A、B開始遍歷鏈表，此時最先遇到空節點(到達末尾)的鏈表即為短鏈表。
curA、curB走過的長度均為LenA。
此時將curA指向鏈表 B (長鏈表)的頭節點，curB 不變。兩個指針開始第二段遍歷，直到 curB 遇到空節點（長鏈表到達末尾）。
此時 curB 走完整個長鏈表，走的第二段長度就是差值 L。CurA 從長鏈表頭節點開始，與 curB 同步，其走的第二段長度同樣是差值 L。
此時 curA 在長鏈表 剩余未遍歷的節點長度是：LenB - L = LenA
此時將 curB 指向鏈表A的頭節點，即將遍歷鏈表A 的長度為 LenA ，則curA、curB剩余即將遍歷的長度即為原本需要比較的長度。
開始第三段遍歷，遇到第一個相同節點時返回即可。
代碼：Java：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode curA = headA;
ListNode curB = headB;
while (curA != curB) {
curA = curA == null ? headB : curA.next;
curB = curB == null ? headA : curB.next;
}
return curA;
}
}
Python：
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if not headA or not headB:
return None
curA , curB = headA , headB
while curA != curB:
curA = curA.next if curA else headB
curB = curB.next if curB else headA
return curA
歡迎關注公眾號一起學習：愛寫Bug
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/45198.html
摘要：示例輸入輸出輸入解釋相交節點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結果后，兩個鏈表仍須保持原有的結構。此時將指向鏈表長鏈表的頭節點，不變。 愛寫Bug（ID：iCodeBugs） 編寫一個程序，找到兩個單鏈表相交的起始節點。 Write a program to find the node at which the i...
摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。 在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區別...
摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：還是鏈表算法題目描述給出兩個無環單鏈表判斷和是否相交。所以可以得出另外一種解法，先遍歷鏈表，記住尾節點，然后遍歷鏈表，比較兩個鏈表的尾節點，如果相同則相交，不同則不相交。想法還是奇妙的。算法寫起來不難，難的是想到這個。 還是鏈表算法 題目描述：給出兩個無環單鏈表A: a1 → a2 ↘ c1 → c2 → c3 → ...
閱讀 1138·2021-11-25 09:43
閱讀 1576·2021-10-25 09:47
閱讀 2472·2019-08-30 13:46
閱讀 758·2019-08-29 13:45
閱讀 1286·2019-08-26 13:29
閱讀 2996·2019-08-23 15:30
閱讀 1110·2019-08-23 14:17
閱讀 1331·2019-08-23 13:43
