C语言实现非降序链表合并 | 附三种解法与代码示例 - 常规

C语言实现非降序链表合并 | 附三种解法与代码示例

本文将介绍如何使用C语言实现两个非降序链表的合并，并提供三种不同思路的解法，帮助你更好地理解和掌握链表操作。

问题描述

已知两个非降序链表序列 S1 与 S2，设计函数构造出 S1 与 S2 合并后的新的非降序链表 S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用 -1 表示序列的结尾（-1 不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出 NULL。

输入样例:

1 3 5 -12 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

解法一：尾插法

思路：

遍历两个链表，逐个比较节点值大小。2. 将较小值的节点连接到新链表的末尾。3. 处理完一个链表后，将另一个链表的剩余部分直接连接到新链表的末尾。

**代码示例：**c#include <stdio.h>#include <stdlib.h>

struct ListNode { int val; struct ListNode *next;};

struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2) { if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; }

struct ListNode* head = NULL;    struct ListNode* tail = NULL;

if (l1->val <= l2->val) {        head = l1;        l1 = l1->next;    } else {        head = l2;        l2 = l2->next;    }    tail = head;

while (l1 && l2) {        if (l1->val <= l2->val) {            tail->next = l1;            l1 = l1->next;        } else {            tail->next = l2;            l2 = l2->next;        }        tail = tail->next;    }

if (l1) {        tail->next = l1;    }    if (l2) {        tail->next = l2;    }

return head;}

// ... (输入输出代码与其他解法相同，此处省略)

解法二：带头节点法

思路：

创建一个带有头节点的新链表。2. 遍历两个链表，逐个比较节点值大小。3. 将较小值的节点连接到新链表的尾部。4. 处理完一个链表后，将另一个链表的剩余部分直接连接到新链表的尾部。5. 最后返回头节点的下一个节点作为新链表的起始节点。

**代码示例：**c#include <stdio.h>#include <stdlib.h>

// ... (结构体定义与其他解法相同，此处省略)

struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2) { if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; }

struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));    struct ListNode* tail = head;

while (l1 && l2) {        if (l1->val <= l2->val) {            tail->next = l1;            l1 = l1->next;        } else {            tail->next = l2;            l2 = l2->next;        }        tail = tail->next;    }

if (l1) {        tail->next = l1;    }    if (l2) {        tail->next = l2;    }

return head->next;}

// ... (输入输出代码与其他解法相同，此处省略)

解法三：递归法

思路：

当其中一个链表为空时，返回另一个链表。2. 比较两个链表头节点的值，将较小的节点作为新链表的头节点。3. 递归地合并剩余的链表部分，并将结果连接到新链表的头节点之后。

**代码示例：**c#include <stdio.h>#include <stdlib.h>

// ... (结构体定义与其他解法相同，此处省略)

struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2) { if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; }

if (l1->val <= l2->val) {        l1->next = mergeLists(l1->next, l2);        return l1;    } else {        l2->next = mergeLists(l1, l2->next);        return l2;    }}

// ... (输入输出代码与其他解法相同，此处省略)

复杂度分析

以上三种解法的时间复杂度均为 O(n+m)，其中 n 和 m 分别是两个链表的长度。这是因为我们需要遍历两个链表的所有节点一次。

总结

本文介绍了三种使用 C 语言合并两个非降序链表的方法，分别是尾插法、带头节点法和递归法。每种方法都有其优缺点，你可以根据实际情况选择合适的方法。