題目

02.07. 鏈表相交

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

圖示兩個鏈表在節點 c1 開始相交：

代碼

1. 計算兩個鏈表的長度

思路： 獲取兩個鏈表的長度，然后根據將兩個鏈表的開始節點從同一長度（相對于后面相等）開始

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""# 計算兩個鏈表的長度，然后從后面的相同長度開始lenA = 0lenB = 0cur = headAwhile cur:cur = cur.nextlenA += 1cur = headBwhile cur:cur = cur.nextlenB += 1curA = headAcurB = headB# 讓長鏈表的指針先走 |lenA - lenB| 步if lenA > lenB:for i in range(lenA - lenB):curA = curA.nextelse:for i in range(lenB - lenA):curB = curB.nextwhile curA:if curA == curB:return curAcurA = curA.nextcurB = curB.nextreturn None

2. 雙指針

思路： 根據快慢法則，走的快的一定會追上走得慢的。
在這道題里，有的鏈表短，他走完了就去走另一條鏈表，我們可以理解為走的快的指針。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""# 雙指針ta, tb = headA, headBwhile ta != tb:ta = ta.next if ta else headBtb = tb.next if tb else headAreturn tb

代碼隨想錄：鏈接