三个月算法进阶--day36
目录
交叉链表
双指针，遍历完短的之后接上长的，遍历完长的之后接上短的，相遇即为交叉结点
避免循环链表：重定位
记录
leetcode第160题相交链表
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return
ptrA = headA
ptrB = headB
while ptrA and ptrB:
if ptrA == ptrB:
return ptrA
ptrA = ptrA.next
ptrB = ptrB.next
if not ptrA:
ptrA = headB
while ptrB:
ptrA = ptrA.next
ptrB = ptrB.next
ptrB = headA
while ptrB:
if ptrA == ptrB:
return ptrA
ptrA = ptrA.next
ptrB = ptrB.next
return
if not ptrB:
ptrB = headA
while ptrA:
ptrA = ptrA.next
ptrB = ptrB.next
ptrA = headB
while ptrA:
if ptrA == ptrB:
return ptrA
ptrA = ptrA.next
ptrB = ptrB.next
return
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
ptrA = headA
ptrB = headB
if not headA or not headB:
return
lengthA = 1
lengthB = 1
while ptrA.next:
ptrA = ptrA.next
lengthA += 1
while ptrB.next:
ptrB = ptrB.next
lengthB += 1
if ptrA != ptrB:
return
if lengthA > lengthB:
headB, headA = headA, headB
ptrA = headA
ptrB = headB
while ptrA:
ptrA = ptrA.next
ptrB = ptrB.next
ptrA = headB
while ptrB:
ptrA = ptrA.next
ptrB = ptrB.next
ptrB = headA
while ptrA:
if ptrA == ptrB:
return ptrB
ptrA = ptrA.next
ptrB = ptrB.next