｜相交連結清單
給你兩個單連結清單的頭節點 headA 和 headB ，請你找出并傳回兩個單連結清單相交的起始節點。如果兩個連結清單不存在相交節點，傳回 null 。
圖示兩個連結清單在節點 c1 開始相交：
題目資料 保證 整個鍊式結構中不存在環。
注意，函數傳回結果後，連結清單必須 保持其原始結構 。
自定義評測：
評測系統 的輸入如下（你設計的程式 不适用 此輸入）：
intersectVal - 相交的起始節點的值。如果不存在相交節點，這一值為 0
listA - 第一個連結清單
listB - 第二個連結清單
skipA - 在 listA 中（從頭節點開始）跳到交叉節點的節點數
skipB - 在 listB 中（從頭節點開始）跳到交叉節點的節點數
評測系統将根據這些輸入建立鍊式資料結構，并将兩個頭節點 headA 和 headB 傳遞給你的程式。如果程式能夠正确傳回相交節點，那麼你的解決方案将被 視作正确答案 。
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at ‘8’
解釋：相交節點的值為 8 （注意，如果兩個連結清單相交則不能為 0）。
從各自的表頭開始算起，連結清單 A 為 [4,1,8,4,5]，連結清單 B 為 [5,6,1,8,4,5]。
在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
輸入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at ‘2’
解釋：相交節點的值為 2 （注意，如果兩個連結清單相交則不能為 0）。
從各自的表頭開始算起，連結清單 A 為 [1,9,1,2,4]，連結清單 B 為 [3,2,4]。
在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。
輸入：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 。
｜題解
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
"""
解題思路:
1.先計算A連結清單和B連結清單的長度
2.讓長的連結清單先走，len(長) - len(短)
3.然後同步先後執行 如果相等 return
"""
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
countA = 0
countB = 0
curA = headA
curB = headB
# 計算連結清單A的長度
while curA:
countA += 1
curA = curA.next
# 計算連結清單B的長度
while curB:
countB += 1
curB = curB.next
A = headA
B = headB
if countA > countB:
return self.perse(countA, countB, A, B)
else:
return self.perse(countB, countA, B, A)
return None
def perse(self, countA, countB, A, B):
diff = countA - countB
count = 0
while A:
if count >= diff:
if A == B:
return A
A = A.next
B = B.next
else:
A = A.next
count += 1