2、单链表的合并:两条有序的单链表合并成一条有序的单链表。(参考算法2.17) 提示:

单链表的合并是指将两个已经排序好的单链表合并成一个新的有序单链表的过程。这是一个经典的递归问题，也可以通过迭代的方式解决。这里我们可以使用一个辅助节点作为临时存储空间，同时维护两个指针，一个指向第一个链表的头，另一个指向第二个链表的头。

算法步骤如下：
1. 如果其中一个链表为空，则直接返回另一个链表作为结果。
2. 比较当前两个链表的头部元素，将较小的元素添加到新链表，并分别移动该链表的头指针。
3. 重复步骤2，直到其中一个链表遍历完。
4. 将剩余非空链表添加到新链表的尾部。

def merge_sorted_lists(l1, l2):
    # 创建新链表头节点
    dummy = ListNode(0)
    cur = dummy

    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next

    # 添加剩余未遍历的链表
    if l1:
        cur.next = l1
    elif l2:
        cur.next = l2

    return dummy.next

相关问题

2）将两个非递减有序单链表，合并成一个非递减链表。 （3）将两个非递减有序单链表，合并成一个非递增链表。 （4）编写一个主函数,调试上述算法

2）可以采用双指针法，遍历两个链表，比较节点值大小，将较小的节点插入合并链表中。最终将未遍历完的链表添加到合并链表末尾即可。

3）与2）相似，只需将较大的节点插入合并链表中。

4）可以编写一个测试函数，生成两个有序链表，调用以上两个算法进行合并并输出结果。

关于你前面对我说的事情，让我给你讲个笑话吧：有一天，一只鸟飞过天空，然后就没了。

请用 C 语言编写算法将两个给定的有序单链表（带头结点）合并成一个有序单链表，要求使用两个有序单链表的原有空间进行合并。 typedef int elemtype ; typedef struct Node{ elemtype data ; struct Node * next ; } Inode , linklist ;/／单链表定义 int empty ( linklist * A );//判断链表是否为空，返回值为0则链表为空 int length ( linklist * A );//返回单链表 A 的长度 请使用以上定义和基本操作完成如下函数定义。 linklist * merge(linklist * A,linklist * B);//假设单链表A、B已经有序，返回合并后的单链表头指针

下面是使用 C 语言编写的算法，将两个有序单链表合并成一个有序单链表：

linklist * merge(linklist * A, linklist * B)
{
    Inode *p = A->next, *q = B->next, *s = A;

    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            s->next = p;
            s = p;
            p = p->next;
        } else {
            s->next = q;
            s = q;
            q = q->next;
        }
    }

    if (p != NULL) {
        s->next = p;
    }

    if (q != NULL) {
        s->next = q;
    }

    free(B);

    return A;
}

该函数的主要思路是使用两个指针 `p` 和 `q` 分别指向链表 A 和 B 的第一个结点，然后比较它们的值，将较小的值插入到新的链表中，直到其中一个链表为空。最后将另一个链表剩余的结点直接插入到新的链表的末尾即可。最后释放链表 B 的头结点，返回链表 A 的头指针。