合并两个有序单链表 - Python 代码实现

合并两个有序单链表 - Python 代码实现

本文将介绍如何使用 Python 代码将两个非递减有序的单链表合并成一个新的非递减有序的单链表。

问题描述:

给定两个单链表 LA 和 LB，其元素均为非递减有序排列。编写算法将它们合并成一个单链表 LC，要求 LC 也是非递减有序排列，要求 LC 利用原表的存储空间。

算法实现:

可以使用双指针法来合并两个有序链表，同时利用原表的存储空间。以下是合并的算法实现：

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

def merge_sorted_lists(la: ListNode, lb: ListNode) -> ListNode:
    # 创建一个哑结点作为合并后链表的头结点
    dummy = ListNode(0)
    lc = dummy

    while la and lb:
        if la.val <= lb.val:
            # la 的值小于等于 lb 的值，将 la 的结点接到 lc 链表上
            lc.next = la
            la = la.next
        else:
            # lb 的值小于 la 的值，将 lb 的结点接到 lc 链表上
            lc.next = lb
            lb = lb.next
        lc = lc.next

    # 将剩余的结点接到 lc 链表上
    if la:
        lc.next = la
    if lb:
        lc.next = lb

    # 返回合并后的链表，去除哑结点
    return dummy.next

代码解释:

1. 创建一个哑结点 dummy，作为合并后的链表的头结点。
2. 使用两个指针 la 和 lb 分别指向 LA 和 LB 的头结点。
3. 使用指针 lc 指向 dummy，用于连接合并后的结点。
4. 循环遍历 LA 和 LB 链表，比较 la.val 和 lb.val 的大小。
5. 如果 la.val 小于等于 lb.val，则将 la 指向的结点连接到 lc 链表上，并将 la 指针向后移动一位。
6. 如果 lb.val 小于 la.val，则将 lb 指向的结点连接到 lc 链表上，并将 lb 指针向后移动一位。
7. 在每次连接后，将 lc 指针向后移动一位。
8. 遍历完 LA 和 LB 链表后，将剩余的结点连接到 lc 链表上。
9. 返回合并后的链表，去除哑结点 dummy。

示例代码:

# 创建链表 LA
la = ListNode(1)
la.next = ListNode(3)
la.next.next = ListNode(5)

# 创建链表 LB
lb = ListNode(2)
lb.next = ListNode(4)
lb.next.next = ListNode(6)

# 合并链表 LA 和 LB
lc = merge_sorted_lists(la, lb)

# 打印合并后的链表 LC
while lc:
    print(lc.val, end=' ')
    lc = lc.next

输出结果:

1 2 3 4 5 6

总结:

使用双指针法和哑结点可以有效地合并两个有序单链表，同时利用原表的存储空间。该算法的时间复杂度为 O(m+n)，其中 m 和 n 分别为两个链表的长度。