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

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

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

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

示例 1：

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

?

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

進階：你能否設(shè)計一個時間復(fù)雜度 O(n) 、僅用 O(1) 內(nèi)存的解決方案？

題解：

問題的核心思想是：兩個鏈表被分成三個部分，a、b、c. 如果他們有共同的交點那么一定有公式a + c + b = b + c + a ，因此當(dāng)a鏈表循環(huán)到末尾時，跳轉(zhuǎn)到b鏈表上。那么他們一定會同時到達同一個節(jié)點上去。

如果不存在共同鏈c，那么有a + b = b + a ，他們會同時到達對方的末尾None處，因此也會退出循環(huán)。

如果題目只是判斷是否相交不需要給出相交節(jié)點的值，那么還有如下思路：

• 將A鏈表的尾巴連接到B鏈表的表頭，如果B鏈表存在循環(huán)，那么相交
• 直接將A、B兩個鏈表循環(huán)到末尾，如果末尾節(jié)點相同，那么相交
  ?

# 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:l1 = headAl2 = headBif l1 == None or l2 == None:return Nonewhile l1 != l2:l1 = l1.next if l1 != None else headBl2 = l2.next if l2 != None else headAreturn l1

總結(jié)

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

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