LeetCode 160.相交链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists

我的蒟蒻想法：

题目要求不能改变原来的链表，所以判断完再接回去，感觉自己牛的不行，马上code

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        tempNode = ListNode()
        preNode = ListNode()
        def lenL(p):
            k = 0
            while  p:
                k += 1
                p = p.next
            return k
        Blen = lenL(headB)
        while headA:
            tempNode.next = headA.next
            tempNode.val = headA.val
            headA.next = None
            if lenL(headB) < Blen:
                headA.next = tempNode.next
                tempNode = headA
                return tempNode
            else:
                headA.next = tempNode.next
                preNode = headA
                headA = headA.next
                
        while headB.next:
            headB = headB.next
        if preNode == headB:
            return headB
        return None

中间没有考虑辩阶情况，就是如果只有一个公共点，我去切他屁股 长度当然不会有变化，思考了一下我就再加一个判断，如果A切完了还是没有，那看看它和B的最后一个一样吗，一样就返回。觉得这下过了吧！

当然没有，555555555555555
果然 超时了
还是去看看大佬的吧

大佬的想法

用两个指针，一个从A开始走，一个从B开始走，走到头就换，第一个相同的点一定是公共点。因为当都走过A+C+B的距离后，会在C的起点相遇。还愣着干什么，一起膜拜~~~

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a