題目描述：
給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并回傳兩個單鏈表相交的起始節點，如果兩個鏈表沒有交點，回傳 null ，
圖示兩個鏈表在節點 c1 開始相交：
題目資料 保證 整個鏈式結構中不存在環，
注意，函式回傳結果后，鏈表必須 保持其原始結構 ，
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '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
輸出：Intersected at '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 ，
提示：
listA 中節點數目為 m
listB 中節點數目為 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 沒有交點，intersectVal 為 0
如果 listA 和 listB 有交點，intersectVal == listA[skipA + 1] == listB[skipB + 1]
進階：你能否設計一個時間復雜度 O(n) 、僅用 O(1) 記憶體的解決方案？
解題思路：
本題目多種解決方案，只放其中一種，
由圖可知，不論兩鏈表是否等長，將兩表按不同先后順序排列起來，組成兩個新表，然后從頭開始共同遍歷，若能找到相等的節點，說明存在相交節點，不存在，則回傳null，
public ListNode getIntersectionNode(ListNode headA, ListNode headB){ //思路，兩個鏈表拼接起來，遍歷，判斷兩鏈表是否數值相等 ListNode curA = headA; ListNode curB = headB; while(curA != curB){ if(headA == null || headB == null) return null; if(curA == null) curA = headB; else curA = curA.next; if(curB == null) curB = headA; else curB = curB.next; } return curA; }
注意：
1.每次遍歷都要判斷鏈表是否為空，若curA為空，說明已經走到A表盡頭，此時應該指向B表頭結點，繼續遍歷，curB也是如此，若有相交節點，便退出回圈，回傳交點，若遍歷到最后，curA == curB == null 退出回圈，說明遍歷到最后，兩節點都為空了，還是不存在相交節點，此時兩點都為空，相等，退出回圈，回傳null，
2.一定先判斷是否為空，不然超時，
時間復雜度O(n)，空間復雜度O(1)，
此題解法非常簡介精妙，用心體會思想
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/300120.html
標籤：其他