[数据结构与算法]160. 相交链表

160. 相交链表

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

解题：

单链表的基本问题

法一：哈希集

用一个集合存下headA中所有的结点，然后检查headB中的结点是否在集合中

时间复杂度O(n+m-k)(k是公共长度)，额外空间复杂度O(n or m)

法二：双指针

令headA为A+K，headB为B+K，K为公共部分

我们定义两个指针，指针1，遍历完headA后（行走了A+K）进入到headB中
同样的，指针2，遍历完headB后（行走了B+K）进入到headA中

当指针1在headB中走了B，指针2在headA中走了A时（两者都走了A+B+K）相遇，且相遇点为相交点。

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

        return node1