題目

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

圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：

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

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

自定義評(píng)測(cè)：

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

intersectVal - 相交的起始節(jié)點(diǎn)的值。如果不存在相交節(jié)點(diǎn)，這一值為 0
listA - 第一個(gè)鏈表
listB - 第二個(gè)鏈表
skipA - 在 listA 中（從頭節(jié)點(diǎn)開始）跳到交叉節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)
skipB - 在 listB 中（從頭節(jié)點(diǎn)開始）跳到交叉節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)
評(píng)測(cè)系統(tǒng)將根據(jù)這些輸入創(chuàng)建鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，并將兩個(gè)頭節(jié)點(diǎn) headA 和 headB 傳遞給你的程序。如果程序能夠正確返回相交節(jié)點(diǎn)，那么你的解決方案將被 視作正確答案 。

示例 1：

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

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

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個(gè)鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個(gè)鏈表不相交，因此返回 null 。
提示：
listA 中節(jié)點(diǎn)數(shù)目為 m
listB 中節(jié)點(diǎn)數(shù)目為 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 沒有交點(diǎn)，intersectVal 為 0
如果 listA 和 listB 有交點(diǎn)，intersectVal == listA[skipA] == listB[skipB]
進(jìn)階：你能否設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度 O(m + n) 、僅用 O(1) 內(nèi)存的解決方案？

來源：力扣（LeetCode）

解題思路

??看完這道題的題目，假設(shè)現(xiàn)在再給定一個(gè)條件，比如A比B長多少，或者B比A長多少，那就好做多了；如果有了這個(gè)條件我們就可以直接讓兩個(gè)鏈表同步走一樣的路，如果相交就能立馬發(fā)現(xiàn)，但遺憾的是并沒有這么一個(gè)好的條件。所謂沒有條件就需要?jiǎng)?chuàng)造條件，我們需要想辦法比出個(gè)長短來，比如，平時(shí)下跳跳棋的時(shí)候一方已經(jīng)獲勝，那么另一方如果想知道差距的話就需要計(jì)算自己還需要多少步能夠完成，在這里也是一樣，我們可以讓兩個(gè)鏈表同步遍歷，一旦有一方到達(dá)了終點(diǎn)，那么我們開始清算另一方還需要多少步才能到達(dá)終點(diǎn)，需要多少步那就是我們所假設(shè)的條件了。得到這個(gè)條件我們讓比較長的那一個(gè)鏈先走上那么幾步，然后兩個(gè)鏈再開始同步遍歷，這個(gè)時(shí)候就比較好查找相交的結(jié)點(diǎn)了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:p1=headAp2=headBcount=0flag=1 #A與B長短標(biāo)記，A長于B為1，B長于A為0while p1 and p2:if p1==p2:  #如果AB一樣長且有交點(diǎn)的話一遍遍歷便可以找到交點(diǎn)return p1p1=p1.nextp2=p2.nextwhile p1:  #第一遍同步遍歷完當(dāng)A還有剩余時(shí)計(jì)算還需多少步flag=1count+=1p1=p1.nextwhile p2: #第一遍同步遍歷完當(dāng)B還有剩余時(shí)計(jì)算還需多少步flag=0count+=1p2=p2.nextif flag:for i in range(count): #A長的話先讓A走幾步headA=headA.nextelse:for i in range(count): #B長的話先讓B走幾步headB=headB.nextwhile headA:if headA==headB:  #如果找到相交的結(jié)點(diǎn)返回即可return headAheadA=headA.nextheadB=headB.next

總結(jié)

以上是生活随笔為你收集整理的LeetCode简单题之相交链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。