編寫(xiě)一個(gè)程序瑞妇，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋?zhuān)合嘟还?jié)點(diǎn)的值為 8 （注意，如果兩個(gè)鏈表相交則不能為 0）实抡。從各自的表頭開(kāi)始算起阁簸，鏈表 A 為 [4,1,8,4,5]授舟，鏈表 B 為 [5,0,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 = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Reference of the node with value = 2
輸入解釋?zhuān)合嘟还?jié)點(diǎn)的值為 2 （注意阔加，如果兩個(gè)鏈表相交則不能為 0）饵史。從各自的表頭開(kāi)始算起，鏈表 A 為 [0,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
輸入解釋?zhuān)簭母髯缘谋眍^開(kāi)始算起尊惰，鏈表 A 為 [2,6,4]讲竿，鏈表 B 為 [1,5]。由于這兩個(gè)鏈表不相交弄屡，所以 intersectVal 必須為 0题禀，而 skipA 和 skipB 可以是任意值。
解釋?zhuān)哼@兩個(gè)鏈表不相交膀捷，因此返回 null迈嘹。
注意：
如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回 null.
在返回結(jié)果后全庸，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)秀仲。
可假定整個(gè)鏈表結(jié)構(gòu)中沒(méi)有循環(huán)。
程序盡量滿足 O(n) 時(shí)間復(fù)雜度壶笼，且僅用 O(1) 內(nèi)存神僵。
解題思路：
我們通常做這種題的思路是設(shè)定兩個(gè)指針?lè)謩e指向兩個(gè)鏈表頭部，一起向前走直到其中一個(gè)到達(dá)末端拌消，另一個(gè)與末端距離則是兩鏈表的 長(zhǎng)度差挑豌。再通過(guò)長(zhǎng)鏈表指針先走的方式消除長(zhǎng)度差安券，最終兩鏈表即可同時(shí)走到相交點(diǎn)。
換個(gè)方式消除長(zhǎng)度差： 拼接兩鏈表氓英。
設(shè)長(zhǎng)-短鏈表為 C侯勉，短-長(zhǎng)鏈表為 D （分別代表長(zhǎng)鏈表在前和短鏈表在前的拼接鏈表），則當(dāng) C 走到長(zhǎng)短鏈表交接處時(shí)铝阐，D 走在長(zhǎng)鏈表中址貌，且與長(zhǎng)鏈表頭距離為 長(zhǎng)度差;
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
ha, hb = headA, headB
while ha != hb:
ha = ha.next if ha else headB
hb = hb.next if hb else headA
return ha
分別為鏈表A和鏈表B設(shè)置指針A和指針B，然后開(kāi)始遍歷鏈表徘键，如果遍歷完當(dāng)前鏈表练对，則將指針指向另外一個(gè)鏈表的頭部繼續(xù)遍歷，直至兩個(gè)指針相遇吹害。
最終兩個(gè)指針?lè)謩e走過(guò)的路徑為：
指針A :a+c+b
指針B :b+c+a
明顯 a+c+b = b+c+a,因而如果兩個(gè)鏈表相交螟凭，則指針A和指針B必定在相交結(jié)點(diǎn)相遇。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
nodeA = headA
nodeB = headB
while(nodeA !=nodeB):
nodeA = nodeA.next if nodeA else headB
nodeB = nodeB.next if nodeB else headA
return nodeA
存鏈表節(jié)點(diǎn)進(jìn)行查詢
（1）遍歷鏈表A它呀，并將其節(jié)點(diǎn)存入集合（2）遍歷B的每個(gè)節(jié)點(diǎn)并在集合中進(jìn)行查詢螺男，一旦遍歷過(guò)程中查詢到相同節(jié)點(diǎn)，即說(shuō)明有交點(diǎn)纵穿，否則無(wú)
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
A = set()
cur1 = headA
cur2 = headB
while cur1:
A.add(cur1)
cur1 = cur1.next
while cur2:
if cur2 in A:
return cur2
cur2 = cur2.next
return None
算出鏈表距離差挨個(gè)對(duì)比
分別遍歷兩個(gè)鏈表下隧，并記錄兩鏈表的長(zhǎng)度差n，將出現(xiàn)兩種情況谓媒，（1）如果遍歷完淆院，尾部的空節(jié)點(diǎn)不是同一節(jié)點(diǎn)（內(nèi)存地址不同），那么必然是不相交
（2）若是同一節(jié)點(diǎn)句惯，則說(shuō)明兩鏈表存在相交土辩，讓長(zhǎng)鏈表先走n步，再同時(shí)開(kāi)始走宗弯，并對(duì)比兩個(gè)鏈表的當(dāng)前節(jié)點(diǎn)脯燃，節(jié)點(diǎn)相等時(shí)即為交點(diǎn)
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
cur1 = headA
cur2 = headB
n = 0
while cur1:
n += 1
cur1 = cur1.next
while cur2:
n -= 1
cur2 = cur2.next
if cur1 != cur2:
return None
cur1 = headA if n > 0 else headB
cur2 = headB if cur1 == headA else headA
n = abs(n)
while n:
n -= 1
cur1 = cur1.next
while cur1 != cur2:
cur1 = cur1.next
cur2 = cur2.next
return cur1
return None
來(lái)源：力扣（LeetCode）
