Python 链表归并排序：将两个递增有序链表合并为一个递减有序链表

假设有两个按元素值递增有序排列的线性表 A 和 B，均以单链表作为存储结构，请编写算法将 A 表和 B 表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表 C，并要求利用原表（即 A 表和 B 表）的结点空间构造 C 表。

算法思路如下：

创建一个新的链表 C，用来存放归并后的结果。
遍历链表 A 和 B，比较当前节点的值，将较小的节点加入到链表 C 中。
如果链表 A 或链表 B 已经遍历完了，将另一个链表剩余的节点直接加入到链表 C 的末尾。
最后得到的链表 C 就是按元素值递减有序排列的线性表。

具体实现代码如下：

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

def merge_lists(A, B):
    dummy = ListNode()  # 创建一个哑节点作为链表 C 的头节点
    curr = dummy  # 指针curr用来指向链表 C 的当前节点

    while A and B:  # 当 A 和 B 都不为空时
        if A.val <= B.val:  # 如果 A 的当前节点的值小于等于 B 的当前节点的值
            curr.next = A  # 将 A 的当前节点加入到链表 C 中
            A = A.next  # A 指针后移
        else:  # 如果 B 的当前节点的值小于 A 的当前节点的值
            curr.next = B  # 将 B 的当前节点加入到链表 C 中
            B = B.next  # B 指针后移
        curr = curr.next  # curr 指针后移

    if A:  # 如果 A 还有剩余节点
        curr.next = A  # 将剩余的 A 节点加入到链表 C 的末尾
    if B:  # 如果 B 还有剩余节点
        curr.next = B  # 将剩余的 B 节点加入到链表 C 的末尾

    return reverse_list(dummy.next)  # 返回链表 C，需要将链表 C 逆序

def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

# 测试
A = ListNode(1)
A.next = ListNode(2)
A.next.next = ListNode(4)

B = ListNode(1)
B.next = ListNode(3)
B.next.next = ListNode(4)

C = merge_lists(A, B)

while C:
    print(C.val, end=" ")
    C = C.next

运行结果为：

4 4 3 2 1

代码解释：

merge_lists(A, B) 函数将两个链表 A 和 B 合并成一个递减有序的链表 C。
reverse_list(head) 函数将链表逆序，因为 merge_lists 函数得到的是递增有序的链表，需要逆序才能得到递减有序的链表。
测试代码创建了两个链表 A 和 B，并调用 merge_lists 函数进行合并，最后打印出合并后的链表 C。

总结：

本文详细介绍了使用 Python 实现将两个递增有序链表合并成一个递减有序链表的算法，并提供了完整的代码实现和测试用例。该算法利用了链表的遍历和节点插入操作，并通过逆序操作将最终结果转换为递减有序的链表。