面试题 02.07. 链表相交

题目描述

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

你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

解题思路

这题没有rust选

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        la = 1
        lb = 1
        ptra = headA
        ptrb = headB
        if ptra is None or ptrb is None:
            return None
        while ptra.next != None:
            la += 1
            ptra = ptra.next
        while ptrb.next != None:
            lb += 1
            ptrb = ptrb.next
        if la < lb:
            ptra, ptrb = headB, headA
        else:
            ptra, ptrb = headA, headB

        d = abs(la - lb)
        print(d, la, lb)
        for i in range(d):
            ptra = ptra.next
        for i in range(min(la,lb)):
            if ptra is ptrb:
                return ptra
            else:
                ptra = ptra.next
                ptrb = ptrb.next
        return None

学习感想

看解析之前没有想到这个做法

重点是尾部对其，