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中，我们可以使用哈希集合（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`是一个辅助函数，用于迭代打印链表节点的值。

求三个非递减线性链表的交集完整代码

求解三个非递减有序链表的交集需要使用一种数据结构处理多个链表，并查找它们的公共元素。这里提供一个Python的解决方案，首先将所有链表合并成一个新的链表，然后遍历这个新链表找出公共节点。以下是完整的代码：

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

def getIntersectionNode(headA, headB):
    # Step 1: Merge the two lists until they meet or one is exhausted
    p1, p2 = headA, headB
    while p1 and p2:
        if p1 == p2:
            return p1
        p1 = headA if p1 == None else p1.next
        p2 = headB if p2 == None else p2.next
    
    # Step 2: If they don't intersect, find the longer list's end
    longer_list = headA if headA != p2 else headB
    shorter_list = p1 if p1 == p2 else headA
    for _ in range(len(longer_list) - len(shorter_list)):
        longer_list = longer_list.next
    
    # Step 3: Compare the ends of the longer list with the second list to find intersection
    return longer_list if longer_list == headB else None

# 示例：
# 假设链表A、B、C分别是 1->3->4->7->9 和 1->2->4->8 和 5->6->7
headA = ListNode(1, ListNode(3, ListNode(4, ListNode(7, ListNode(9)))))
headB = ListNode(1, ListNode(2, ListNode(4, ListNode(8))))
headC = ListNode(5, ListNode(6, ListNode(7)))

intersection = getIntersectionNode(headA, headB)
if intersection:
    print("Intersection nodes are:", [node.val for node in iterate_nodes(intersection)])
else:
    print("No intersection")

def iterate_nodes(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result