python求链表交集

要求两个链表的交集，我们可以先把链表元素存储到两个集合中，然后遍历其中一个链表，在另一个集合中查找是否存在相同元素。如果存在，则加入结果集合中。以下是Python代码实现：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    node_set = set()
    while headA:
        node_set.add(headA)
        headA = headA.next
    while headB:
        if headB in node_set:
            return headB
        headB = headB.next
    return None

相关问题

python实现链表相交

### Python 实现检测链表是否相交

为了判断两个单链表是否存在相交节点，可以采用多种策略。一种常见的高效方法是利用双指针技术，在不增加额外空间复杂度的情况下完成此操作。

#### 方法概述
定义两个指针分别指向两条链表的头部并同步前进。当任意一个指针到达链表末端时，则将其重定向至另一条链表的头部继续移动。最终，如果两链表有交点，那么这两个指针会在第一次相遇处即为所求交点；如果没有交点，则二者会同时抵达各自链表结尾(null)，此时返回None表示无交集[^1]。

下面是具体的Python代码实现：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None
    
    pointerA, pointerB = headA, headB
    
    while pointerA is not pointerB:
        # 当pointerA走到尽头则转向headB重新开始遍历
        pointerA = headB if not pointerA else pointerA.next
        
        # 同理对于pointerB也做相同的操作
        pointerB = headA if not pointerB else pointerB.next
        
    return pointerA  # 返回交点 或者 None 如果没有交点

该函数接收两个参数`headA`和`headB`作为输入，代表要比较的两个链表的头结点。通过上述逻辑能够有效地找出第一个公共节点的位置或确认两者之间并无任何交叉部分[^2]。

python两个单链表求交集代码

在Python中，我们可以使用哈希集合（set）来找出两个单链表的交集部分。以下是递归实现的一个简单例子：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA, headB):
    if not headA or not headB:
        return None
    
    # 将链表A和B都遍历到头，找到它们的公共节点
    pA, pB = headA, headB
    while pA != pB:
        if pA:
            pA = pA.next
        else:
            pA = headB
        if pB:
            pB = pB.next
        else:
            pB = headA
            
    # 返回公共链表的头节点
    return pA

# 示例链表节点定义
node1 = ListNode(1)
node1.next = ListNode(2)
node1.next.next = ListNode(3)
node1.next.next.next = ListNode(4)

node2 = ListNode(5)
node2.next = ListNode(6)
node2.next.next = node1.next.next.next  # 这里使得第二个链表有相同的交集部分

intersection = getIntersectionNode(node1, node2)
if intersection:
    print("Intersection nodes are:", [node.val for node in iterateListNode(intersection)])
else:
    print("No intersection")

def iterateListNode(node):
    while node:
        yield node
        node = node.next

在这个代码中，`getIntersectionNode`函数首先检查两个链表是否为空，然后通过移动指针的方式找到它们的第一个公共节点。`iterateListNode`是一个辅助函数，用于迭代打印链表节点的值。