如何不创建新节点实现两个有序链表的无重复并集合并

核心修改思路 #

• 移除原实现中新建的dummyNode占位节点，完全复用两个原始链表的已有节点，仅修改节点的next指针指向
• 利用输入链表本身有序的特性，合并过程中同步跳过重复值，无需后续单独执行全量去重操作，同时将时间复杂度从原来的O((n+m)^2)优化到O(n+m)
• 全程没有任何新节点创建操作，完全符合规则要求

修改后的完整Union函数代码 #

def Union(a, b):
    # 处理空链表边界场景
    if a is None:
        return b
    if b is None:
        return a
    
    # 选择两个链表首节点中值更小的作为结果链表头，不新建节点
    if a.data <= b.data:
        head = a
        a = a.next
    else:
        head = b
        b = b.next
    tail = head

    # 提前跳过两个链表中所有和头节点值重复的节点
    while a and a.data == tail.data:
        a = a.next
    while b and b.data == tail.data:
        b = b.next

    # 循环合并两个链表的剩余节点
    while a and b:
        if a.data <= b.data:
            current = a
            a = a.next
            # 跳过a链表中所有和当前值重复的节点
            while a and a.data == current.data:
                a = a.next
        else:
            current = b
            b = b.next
            # 跳过b链表中所有和当前值重复的节点
            while b and b.data == current.data:
                b = b.next
        # 将无重复的当前节点接入结果链表尾部
        tail.next = current
        tail = tail.next
    
    # 拼接a链表剩余的无重复节点
    while a:
        if a.data != tail.data:
            tail.next = a
            tail = tail.next
        a = a.next
    # 拼接b链表剩余的无重复节点
    while b:
        if b.data != tail.data:
            tail.next = b
            tail = tail.next
        b = b.next
    # 断开尾部可能存在的重复节点链接
    tail.next = None

    return head

实现效果说明 #

针对你给出的示例输入：

• L1节点值：2 3 3 4 4 4 5
• L2节点值：3 4 5 5 6 7
  上述实现返回的结果链表值序列为2 3 4 5 6 7，完全符合预期输出要求。

内容的提问来源于stack exchange，提问作者Marian