相交链表

2025/10/16

我的思路：每个链表从头指针开始，交替向前推进，每步推进作一次判断是否指向同一个节点。

手写代码：

class Node:
    def __init__(self, val):
        self.val = val
        self.next: Node

def IntersectionNode(A: Node, B: Node):
    alter = 0
    while notsame(A, B):
        if alter == 0:
            A = A.next
            alter = 1
        elif alter == 1:
            B = B.next
            alter = 0
    return A

答案：思路是错的，因为可能会错过

我的思路2：暴力遍历，对每个A节点，遍历一遍B

答案：可以，但是不推荐

推荐解法：

1. 双指针法：不够直观，我想不出来；
2. 哈希算法减少复杂度：先遍历一个链表，用字典存起来，再用另一个去查。可以想得到，但我当时没这么想。