合并两个有序单向链表

简介

本文档介绍了一种使用C语言将两个有序单向链表合并成一个有序单向链表的方法。本文档包含算法的解释、完整的代码实现以及示例用法。

算法解释

将两个有序单向链表合并成一个有序单向链表的基本思路如下：

初始化：创建一个哑节点(dummy node)作为新链表的起始点，以简化操作。
合并过程：比较两个链表的头节点，选择较小的节点作为新链表的下一个节点，移动相应链表的指针，重复此过程直到其中一个链表为空。
处理剩余节点：将非空链表的剩余节点直接连接到新链表的末尾。
返回结果：返回哑节点的下一个节点作为合并后的链表的头节点。

在最优情况下，合并两个长度均为N的有序链表的最少比较次数为(2N - 1)。

完整代码

下面是完整的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct ListNode {
    int val;
    struct ListNode* next;
};

// 创建新节点
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 创建一个哑节点作为新链表的起始点
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;
    
    // 合并两个链表
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    // 将剩余的节点连接到新链表末尾
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }
    
    return dummy.next;
}

// 打印链表
void printList(struct ListNode* head) {
    while (head != NULL) {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

// 释放链表内存
void freeList(struct ListNode* head) {
    struct ListNode* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    // 创建第一个有序链表: 1 -> 3 -> 5
    struct ListNode* l1 = createNode(1);
    l1->next = createNode(3);
    l1->next->next = createNode(5);
    
    // 创建第二个有序链表: 2 -> 4 -> 6
    struct ListNode* l2 = createNode(2);
    l2->next = createNode(4);
    l2->next->next = createNode(6);
    
    // 合并链表
    struct ListNode* mergedList = mergeTwoLists(l1, l2);
    
    // 打印合并后的链表
    printf("Merged List: ");
    printList(mergedList);
    
    // 释放链表内存
    freeList(mergedList);
    
    return 0;
}

使用示例

输入

假设我们有两个有序链表：

第一个链表：1 -> 3 -> 5
第二个链表：2 -> 4 -> 6

运行结果

合并后的链表为：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

代码说明

结构定义：
- struct ListNode 定义了链表节点的结构，包含一个整数值和指向下一个节点的指针。
节点创建：
- createNode 函数用于创建新节点。
合并函数：
- mergeTwoLists 函数接收两个有序链表的头节点，返回合并后的有序链表的头节点。
- 使用哑节点 dummy 作为合并后链表的起始点，以简化操作。
- 逐一比较两个链表的节点，将较小的节点链接到新链表，并移动对应链表的指针。
- 最后，将未处理完的链表节点直接连接到新链表末尾。
打印函数：
- printList 函数用于打印链表的所有节点值。
释放内存：
- freeList 函数用于释放链表所占用的内存。
主函数：
- 创建两个示例有序链表。
- 调用 mergeTwoLists 函数合并链表并打印结果。
- 释放合并后的链表内存。

比较次数分析

如果一个链表的所有元素都小于另一个链表的所有元素，那么确实只需要进行 (N) 次比较。这种情况下，一个链表的所有结点会直接被合并进结果链表，然后再将另一个链表的所有剩余结点直接接在结果链表后面，不需要进一步的比较。

最少比较次数（特殊情况）：在极端情况下，如果链表A的所有结点都小于链表B的所有结点，只需要比较N次。例如，链表A的每个结点都比链表B的第一个结点小，那么我们可以在N次比较后将链表A完全合并到结果链表中，然后将链表B的所有结点追加到结果链表中。这时，只需要N次比较。
最坏情况（常规情况）：在最坏的情况下，每次比较后，都会选择两个链表中较小的那个结点加入结果链表中，然后再进行下一次比较。这种情况下，总共有2N个结点需要处理，每次比较后都会将一个结点加入结果链表，因此需要 (2N - 1) 次比较。

总结

最少比较次数： (N) 次（当一个链表的所有元素都小于另一个链表的所有元素时）。
最坏比较次数： (2N - 1) 次（一般情况下，需要交替比较和合并两个链表的所有结点）。

因此，最少比较次数确实是N次。最坏情况下，则需要 (2N - 1) 次比较。

简介​

算法解释​

完整代码​

使用示例​

输入​

运行结果​

代码说明​

比较次数分析​

总结​

简介