Python合并两个有序链表

题目

合并两个有序链表，如l1=[1,3,4], l2=[1,2,4,5]，合并后l3=[1,1,2,3,4,4,5]

解决思路

1. 需要构建节点Node和链表LinkedList结构
2. 如果root节点不确定，可以创建一个哑节点Node(0)，作为root节点的前节点，也是初始节点(当前节点)
3. 循环当l1当前节点不为None并且l2当前节点不为None时，那个节点值小，则当前节点.next=该节点，该节点后移一位
4. 判断l1和l2当前那个有剩余(该链表当前节点不为None)，则将当前节点.next=该节点

实现代码

节点Node及LinkedList类

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

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


class LinkedList:
    def __init__(self, root):
        self.root = root

    def __str__(self):
        values = []
        node = self.root
        while node is not None:
            values.append(node.value)
            node = node.next
        return str(values)

    @classmethod
    def from_list(cls, values):
        node = None
        for value in values[::-1]:
            node = Node(value, node)
        return cls(node)

这里的__str__和from_list方法只是为了方便使用及显示，可以移除

列表融合方法

def merge_linked_lists(list1, list2):
    # 创建一个哑节点作为合并后链表的头节点
    cur = pre_root = Node(0)
    list1_node, list2_node = list1.root, list2.root
    # 迭代比较两个链表的节点值，将较小的节点连接到合并后的链表中
    while list1_node is not None and list2_node is not None:
        if list1_node.value <= list2_node.value:
            cur.next = list1_node
            list1_node = list1_node.next
        else:
            cur.next = list2_node
            list2_node = list2_node.next
        cur = cur.next

    # 将剩余的节点连接到合并后的链表中
    if list1_node is not None:
        cur.next = list1_node

    if list2_node is not None:
        cur.next = list2_node

    return LinkedList(root=pre_root.next)


if __name__ == '__main__':
    l1 = LinkedList.from_list([1, 2,  4])
    l2 = LinkedList.from_list([1, 3,  4, 5])
    l3 = merge_linked_lists(l1, l2)
    print(l3)