合并两个递增有序链表：空间优化算法

合并两个递增有序链表：空间优化算法

本文介绍一种将两个递增有序链表合并为一个递增有序链表的算法，该算法无需额外占用空间，直接利用原链表存储空间进行合并。算法使用双指针方法，遍历两个链表，比较节点大小，并将较小的节点接到结果链表末尾。

思路

1. 使用双指针方法，分别遍历两个有序链表。
2. 比较两个指针指向的节点的大小，将较小的节点接到结果链表的末尾。
3. 直到其中一个链表为空，将另一个链表接到结果链表的末尾即可。

代码实现

def merge_sorted_lists(l1, l2):
    '''
    将两个递增的有序链表合并为一个递增的有序链表
    :param l1: 递增的有序链表1
    :param l2: 递增的有序链表2
    :return: 合并后的递增有序链表
    '''
    if not l1:
        return l2
    if not l2:
        return l1
    # 将结果链表指向l1的头节点
    if l1.val <= l2.val:
        head = l1
        p1 = l1.next
        p2 = l2
    else:
        head = l2
        p1 = l1
        p2 = l2.next
    cur = head
    # 双指针遍历两个有序链表
    while p1 and p2:
        if p1.val <= p2.val:
            cur.next = p1
            p1 = p1.next
        else:
            cur.next = p2
            p2 = p2.next
        cur = cur.next
    # 将剩余节点接到结果链表的末尾
    if p1:
        cur.next = p1
    if p2:
        cur.next = p2
    return head

测试

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

def create_sorted_list(nums):
    '''
    创建一个递增的有序链表
    :param nums: 递增数组
    :return: 递增的有序链表
    '''
    head = ListNode(None)
    cur = head
    for num in nums:
        cur.next = ListNode(num)
        cur = cur.next
    return head.next

def print_list(l):
    '''
    打印链表
    '''
    while l:
        print(l.val, end=' ')
        l = l.next
    print()

l1 = create_sorted_list([1, 3, 5, 7, 9])
l2 = create_sorted_list([2, 4, 6, 8, 10])
l = merge_sorted_lists(l1, l2)
print_list(l)  # 输出：1 2 3 4 5 6 7 8 9 10

总结

该算法通过双指针方法，巧妙地利用了原链表的空间，避免了额外空间的占用，提高了算法的效率。同时，代码简洁易懂，易于理解和实现。