2025/7/19

题目（easy):

---

我的思路：

一开始想的是用双指针，对两个链表同时遍历，然后当两个指针指向同一个结点的时候就返回这个结点即可。但是实际写了下发现不行，观察再多想一下之后发现是因为两个链表在相交之前的部分的结点数并不相同，所以会导致当一个指针指向相交结点了，另一个结点却还没指向相交结点的情况。所以我们只要针对思考如何解决这个问题就好啦。

造成这个情况的原因主要是两个链表的长度不同导致的，那我们想办法让两个链表的长度相同对齐就是了。那对于这题，对齐肯定是长的对齐短的，所以考虑把长的链表的遍历起始位置和短的链表对齐即可

那如何进行这个对齐呢？通过先知道两个链表的长度，然后相减即可得到需要长链表遍历指针对齐的位移量

代码如下：

# 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) -> Optional[ListNode]:
        pa,pb = headA,headB
        lenA, lenB = 0, 0

        #先计算两个链表的长度
        while pa != None:
            pa = pa.next
            lenA += 1
        while pb != None:
            pb = pb.next
            lenB += 1

        #然后把比较长的链表的起始位置和短的对其
        pa,pb = headA,headB
        if lenA > lenB:
            for i in range(lenA-lenB):
                pa = pa.next
        elif lenA < lenB:
            for i in range(lenB-lenA):
                pb = pb.next
        
        #然后从这两个开头的 位置指针往后移动
        while pa != None and pb != None:
            if pa == pb:
                return pa
            else:
                pa = pa.next
                pb = pb.next

        return None

时间复杂度：O（M+N)       【M，N分别是链表A，B的长度】

空间复杂度：O（1）

---

优化思路：

还有一种不直接通过计算链表各自长度进行对齐的方法是当指针pa/pb遍历完A/B链表的时候，让它再指向B/A链表的开头位置，这是因为短的链表的遍历一定会先完成，因此会先回到长链表的开头位置。长链表的遍历则一定会后完成，因此会后回到短链表的开头位置。然后因为pa,pb一直是在同时更新的，所以当长链表的指针回到短链表指针的开头位置的时候，之前从短链表回到长链表开头位置的指针也正好往后移动了和长链表相差位置的个结点，从而正好使两个指针的位置对齐了。

代码如下：

# 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) -> Optional[ListNode]:
        pa,pb = headA,headB
        if pa == None or pb == None:
            return None
        
        #直到使得pa和pb指向同一结点或者都为None位置
        while pa != pb:
            pa = pa.next if pa != None else headB
            pb = pb.next if pb != None else headA

        #当pa == pb之后就说明找到相交点或者为None了
        return pa

时间复杂度：O（M+N）【M，N分别是链表A，B的总长度】

空间复杂度：O（1）

---

其他思路：

直接用哈希表，先遍历存储A的结点，再遍历B中结点和已经存储在哈希表中的结点进行比对即可。思路比较简单，代码就不写了。（偷懒）

时间复杂度：O（M+N）【M，N分别是链表A，B的长度】

空间复杂度：O（M）【M是链表A长度】

---

总结：

①对于和链表打交道的题，对指针的灵活运用总是很关键的

②对于让两个链表起始位置对齐的方式，除了直接计算偏移量值，也可以通过让双指针遍历完一个链表之后再去回到另一个链表的开头来实现