设有带头结点单链表A和B,其结点均已按值升序排列,编写一个算法将他们合并成一个按值升序排列的带头结点单链表。 用数据结构与算法写

为了将两个已按值升序排列的带头结点单链表 A 和 B 合并成一个新的升序链表，我们可以采用迭代或递归的方式。这里我会描述一种简单易理解的迭代方法：

1. 初始化一个新的链表 C，使其头节点指向 null，并创建两个指针 pA 指向 A 的头节点，pB 指向 B 的头节点。

2. 使用 while 循环，直到其中一个指针为空：
a. 如果 pA 或 pB 都不为空，比较它们的值。如果 pA 的值小于等于 pB 的值，则将 pA 的下一个节点（A链表的当前节点）链接到 C 的尾部，然后更新 pA 为 pA 的下一个节点；否则，将 pB 的下一个节点链接到 C 的尾部，然后更新 pB 为 pB 的下一个节点。
b. 如果只有一个指针不为空，将其剩余部分直接添加到链表 C 的尾部。

3. 当循环结束时，链表 C 就是合并后的升序链表。链表 C 的头节点就是原 A 或 B 中剩下的那个非空链表的头节点。

以下是伪代码形式的算法：

def merge_sorted_lists(A, B):
    # 创建新链表 C
    head_C = None
    tail_C = None

    # 迭代合并
    while A and B:
        if A.value <= B.value:
            if not head_C:
                head_C = A
            else:
                tail_C.next = A
            A = A.next
        else:
            if not head_C:
                head_C = B
            else:
                tail_C.next = B
            B = B.next

    # 添加剩余链表
    if A:
        tail_C.next = A
    elif B:
        tail_C.next = B

    return head_C