Python实现不修改原链表的有序链表合并时出现无限循环求排查

问题根因 #

• 直接修改原链表节点导致循环：你的add_at_head方法会直接修改传入节点的next属性，而你传入的是原链表的节点，这会覆盖原节点原本指向原链表下一个节点的next值。后续执行node1 = node1.next/node2 = node2.next时，拿到的已经不是原链表的下一个节点，而是新链表的节点，最终形成遍历环导致无限循环。同时这也违反了「不修改输入原链表」的要求。
• 头插法导致链表顺序颠倒：你用头插法添加节点，得到的新链表本身是倒序的，即使通过反向打印输出结果看起来正确，实际链表结构不符合有序要求。
• 边界返回不符合需求：其中一个输入链表为空时，你直接返回原链表的打印结果，没有返回新的独立链表。

修复方案 #

1. 合并时创建全新的Node实例，不复用原链表节点，避免修改原链表
2. 改用尾插法构建新链表，保证节点顺序和预期一致
3. 修正边界处理逻辑，空输入时也返回新的独立链表
4. 函数最终返回构建完成的新链表对象，而不是直接打印

修正后代码 #

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

    def __str__(self):
        return str(self.data)


class LinkedList:
    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None  # 新增尾指针方便尾插

    def print_list(self):
        node = self.head
        while node is not None:
            print(node, end=' ')
            node = node.next
        print('')

    def add_at_head(self, node):
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.length += 1
    
    # 新增尾插方法
    def add_at_tail(self, node):
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.length += 1

    def remove_node_after(self, node):
        if node.next is not None:
            temp = node.next
            node.next = node.next.next
            temp.next = None
            self.length -= 1
            if temp == self.tail:
                self.tail = node

    def remove_first_node(self):
        if self.head is None:
            return
        temp = self.head
        self.head = self.head.next
        temp.next = None
        self.length -= 1
        if self.head is None:
            self.tail = None

    def print_backward(self):
        def print_nodes_backward(node):
            if node.next is not None:
                print_nodes_backward(node.next)
            if node is not None:
                print(node, end=' ')

        if self.head is not None:
            print_nodes_backward(self.head)

        print('')


def merge_linked_lists(linked_list_1, linked_list_2):
    # 合并两个有序链表，返回全新的独立链表
    new_ll = LinkedList()
    node1 = linked_list_1.head
    node2 = linked_list_2.head

    while node1 is not None and node2 is not None:
        if node1.data <= node2.data:
            # 创建新节点，不修改原节点
            new_ll.add_at_tail(Node(node1.data))
            node1 = node1.next
        else:
            new_ll.add_at_tail(Node(node2.data))
            node2 = node2.next
    
    # 处理剩余节点
    while node1 is not None:
        new_ll.add_at_tail(Node(node1.data))
        node1 = node1.next
    while node2 is not None:
        new_ll.add_at_tail(Node(node2.data))
        node2 = node2.next
    
    return new_ll

测试示例 #

# 构造测试用例
ll1 = LinkedList()
ll1.add_at_tail(Node(1))
ll1.add_at_tail(Node(5))

ll2 = LinkedList()
ll2.add_at_tail(Node(2))

# 合并测试
merged_ll = merge_linked_lists(ll1, ll2)
merged_ll.print_list() # 输出：1 2 5
# 验证原链表未被修改
ll1.print_list() # 输出：1 5
ll2.print_list() # 输出：2

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