leetcode with python:160. Intersection of Two Linked Lists

题目:

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

给定两个linked list,假如两者在某一点交会变同一条,回传该点
若都无交会,回传None

本来我想到的是做记号或是reverse,让我们比较好找到交会点
但题目有特别说linked list要维持原样,因此这些方法都不可行
最后我想到的方案是将两者对齐

# 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) -> Optional[ListNode]:        lenA=0        lenB=0        A=headA        B=headB        while A:            lenA=lenA+1            A=A.next        while B:            lenB=lenB+1            B=B.next                    i=abs(lenA-lenB)        if lenB>lenA:            for j in range(i):                headB=headB.next        else:            for j in range(i):                headA=headA.next                        while headA and headB:            if headA==headB:                return headA            headA=headA.next            headB=headB.next        return  None

因为两个linked list从交会点到尾端的距离是一样的
所以我们让两个linked list在尾端对齐
让短的linked list从头,长的linked list从短linked list头对齐到的位置出发
这样两个指标就会同时到交会点或尾端
所以我们量了两个linked list的长度
透过它们将长linked list的起始点移到对其到短linked list头的位置
开始遍历就能知道交会点是否存在及其位置了
最后执行时间164ms(faster than 92.83%)

但上面那个办法需要先量测长度,稍微慢了些
我在讨论区看到了一个无需测量长度的解法,十分简洁

# 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) -> Optional[ListNode]:        a=headA        b=headB        while a!=b:            if a==None:                a=headB            else:                a=a.next            if b==None:                b=headA            else:                b=b.next        return a

两个linked list都从头开始跑,跑到底就换从另一个linked list的头开始跑
这样两个指标移动最长都会跑到len(linked list1)+len(linked list2)的距离
如此过程中就会达到对齐的效果
因为当长linked list的指标跑完从短linked list的头开始时
跑完短linked list的指标已经在长linked list上跑完两者长度差的长度了
接着就看它们遇到相同的点即为交会点
最后执行时间155ms(faster than 98.27%)

那我们下题见