題目

給你兩個單鏈表的頭節(jié)點?headA?和?headB?，請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表不存在相交節(jié)點，返回?null?。

圖示兩個鏈表在節(jié)點?c1?開始相交：

題目數(shù)據(jù)?保證?整個鏈式結(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須?保持其原始結(jié)構(gòu)?。

自定義評測：

評測系統(tǒng)?的輸入如下（你設(shè)計的程序?不適用?此輸入）：

• intersectVal?- 相交的起始節(jié)點的值。如果不存在相交節(jié)點，這一值為?0
• listA?- 第一個鏈表
• listB?- 第二個鏈表
• skipA?- 在?listA?中（從頭節(jié)點開始）跳到交叉節(jié)點的節(jié)點數(shù)
• skipB?- 在?listB?中（從頭節(jié)點開始）跳到交叉節(jié)點的節(jié)點數(shù)

評測系統(tǒng)將根據(jù)這些輸入創(chuàng)建鏈式數(shù)據(jù)結(jié)構(gòu)，并將兩個頭節(jié)點?headA?和?headB?傳遞給你的程序。如果程序能夠正確返回相交節(jié)點，那么你的解決方案將被?視作正確答案?。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
在 A 中，相交節(jié)點前有 2 個節(jié)點；在 B 中，相交節(jié)點前有 3 個節(jié)點。
— 請注意相交節(jié)點的值不為 1，因為在鏈表 A 和鏈表 B 之中值為 1 的節(jié)點 (A 中第二個節(jié)點和 B 中第三個節(jié)點) 是不同的節(jié)點。換句話說，它們在內(nèi)存中指向兩個不同的位置，而鏈表 A 和鏈表 B 中值為 8 的節(jié)點 (A 中第三個節(jié)點，B 中第四個節(jié)點) 在內(nèi)存中指向相同的位置。

示例?2：

輸入：intersectVal?= 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節(jié)點的值為 2 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [1,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節(jié)點前有 3 個節(jié)點；在 B 中，相交節(jié)點前有 1 個節(jié)點。

示例?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?中節(jié)點數(shù)目為?m
• listB?中節(jié)點數(shù)目為?n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果?listA?和?listB?沒有交點，intersectVal?為?0
• 如果?listA?和?listB?有交點，intersectVal == listA[skipA] == listB[skipB]

解答

源代碼

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA ==null || headB == null) {return null;}ListNode pA = headA, pB = headB;while (pA != pB) {if (pA == null) {pA = headB;} else {pA = pA.next;}if (pB == null) {pB = headA;} else {pB = pB.next;}}return pA;}
}

總結(jié)

學習了題解區(qū)的思路，A鏈表不相交部分長度為a，B鏈表不相交部分為b，相交部分為c，雖然兩鏈表長度不同，但遍歷完當前鏈表后再從頭遍歷另一個鏈表，這時兩指針會在相交點相遇，經(jīng)過的路程為a + b + c。