第2关：基于链表的两个递增有序序列的合并 300 任务要求 参考答案 评论 关卡排行榜 任务描述 编程要求 输入 输出 测试说明 来源 任务描述 本关任务：给定两个递增的整数序列a和b，利用链表表示序

本关任务的要求是将两个递增的整数序列a和b合并成一个递增的整数序列，并利用链表表示。

对于这个任务，可以采用以下算法步骤：

1. 定义一个新的链表头节点res和一个指向res的指针p，并初始化res为NULL。
2. 初始化指向序列a和b的指针pa和pb，分别指向a和b的头节点。
3. 进入循环，直到pa和pb均为NULL：
1. 如果pa为NULL，则将指针p的next指向pb，并将pb后移一位。
2. 如果pb为NULL，则将指针p的next指向pa，并将pa后移一位。
3. 如果pa和pb均不为NULL：
- 比较pa和pb指向的节点的值，如果pa的值小于等于pb的值，则将指针p的next指向pa，并将pa后移一位。
- 否则，将指针p的next指向pb，并将pb后移一位。
4. 将指针p后移一位，即p = p->next。
4. 返回链表res，并输出合并后的链表表示的序列。

这样就能够将两个递增的整数序列合并成一个递增的整数序列，并利用链表表示。算法时间复杂度为O(m+n)，其中m和n分别为序列a和序列b的长度。

相关问题

任务要求 参考答案 评论 任务描述 编程要求 测试说明 任务描述 本关任务:用链表 l

完成一个简单的链表操作，包括链表的创建、插入节点、删除节点以及遍历打印链表的功能。

参考答案

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

def create_linked_list(arr):
    dummy = ListNode()
    current = dummy
    for num in arr:
        current.next = ListNode(num)
        current = current.next
    return dummy.next

def insert_node(head, index, value):
    if index < 0:
        return head
    new_node = ListNode(value)
    if index == 0:
        new_node.next = head
        return new_node
    current = head
    for _ in range(index - 1):
        if current is None:
            return head
        current = current.next
    new_node.next = current.next
    current.next = new_node
    return head

def delete_node(head, index):
    if head is None:
        return None
    if index == 0:
        return head.next
    current = head
    for _ in range(index - 1):
        if current is None:
            return head
        current = current.next
    if current.next is not None:
        current.next = current.next.next
    return head

def print_linked_list(head):
    current = head
    while current is not None:
        print(current.value, end=' ')
        current = current.next
    print()

评论
这是一个简单但是实用的链表操作示例，包括链表的创建、插入、删除和遍历功能，非常适合初学者进行练习。

任务描述
实现链表操作的相关函数，包括创建链表、插入节点、删除节点和打印链表。

编程要求
使用 Python 编写链表操作的相关函数。

测试说明
针对创建链表、插入节点、删除节点和打印链表的功能进行单元测试，确保每个函数的功能正常。

基于链表的两个递增有序序列的合并

假设我们有两个递增有序链表L1和L2，我们可以使用双指针来遍历这两个链表，并将它们合并成一个新的递增有序链表L3。

具体步骤如下：

1. 创建一个新链表L3，以及两个指针p1和p2，分别指向L1和L2的头节点。

2. 比较p1和p2指向的节点的值，将较小的节点加入到L3中，并将对应的指针向后移动一位。

3. 重复上述步骤，直到其中一个链表遍历完毕。

4. 将另一个链表剩余的节点依次加入到L3中。

5. 返回新链表L3。

下面是一个示例代码，可以参考一下：

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 创建新链表和双指针
    ListNode *dummy = new ListNode(-1);
    ListNode *p1 = l1, *p2 = l2, *p3 = dummy;

    // 遍历两个链表，比较大小
    while (p1 && p2) {
        if (p1->val < p2->val) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }

    // 将剩余节点加入新链表
    if (p1) p3->next = p1;
    if (p2) p3->next = p2;

    // 返回新链表
    return dummy->next;
}