如何判断两个单链表是否相交

# 1. 单链表基础知识

#### 1.1 什么是单链表
单链表是一种常见的数据结构，由节点组成，每个节点包含数据和一个指向下一个节点的指针。单链表可以动态地增删节点，不需要连续的内存空间，具有灵活性。

#### 1.2 单链表的节点结构
单链表节点通常包含两部分：数据域用来存储数据，指针域用来指向下一个节点。节点结构定义如下：

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

在单链表中，每个节点都有一个指针指向下一个节点，最后一个节点的指针指向空。单链表的节点结构为链式存储，便于插入和删除操作。

# 2. 判断两个单链表是否相交

#### 2.1 预备知识：单链表的长度和相交点

在判断两个单链表是否相交之前，首先需要了解单链表的长度和相交点的概念。单链表的长度即是链表中节点的个数，而两个单链表相交的定义是它们有共同的节点，即某一个节点的 next 指针指向了同一地址，形成了“Y”字型的结构。

#### 2.2 方法一：暴力法比较每个节点

暴力法的思路是遍历第一个链表的每个节点，然后在第二个链表中查找是否有相同地址的节点。时间复杂度较高，为O(mn)。代码实现如下：

def is_intersect(headA, headB):
    currA = headA
    while currA:
        currB = headB
        while currB:
            if currA == currB:
                return True
            currB = currB.next
        currA = currA.next
    return False

#### 2.3 方法二：利用哈希表记录节点地址

通过使用哈希表，可以将第一个链表中的节点地址存储起来，然后再遍历第二个链表时，查找哈希表中是否存在相同地址的节点。时间复杂度为O(m+n)，空间复杂度为O(m)或O(n)。代码实现如下：

def is_intersect(headA, headB):
    nodes_set = set()
    currA = headA
    while currA:
        nodes_set.add(currA)
        currA = currA.next
    currB = headB
    while currB:
        if currB in nodes_set:
            return True
        currB = currB.n