1. 理解问题
将两个有序的单链表合并成一个新的单链表，并且保持有序。每个链表的元素按照升序排列，合并后的链表也需要保持升序。
示例：
假设我们有两个有序链表：
- 链表 1：1 -> 3 -> 5
- 链表 2：2 -> 4 -> 6
合并后的链表应该是：1 -> 2 -> 3 -> 4 -> 5 -> 6
关键点：
- 两个链表中的每个结点都已经有序。
- 我们需要逐步比较两个链表的当前结点，并将较小的结点插入新的链表中，直到两个链表都为空。
2. 输入输出
输入：
- 两个有序单链表的头结点
head1和head2。
输出：
- 合并后新的有序单链表的头结点。
3. 链表结构
每个链表结点的定义如下：
struct ListNode {
int val; // 节点的值
struct ListNode *next; // 指向下一个节点的指针
};
4. 制定策略
为了将两个有序单链表合并为一个有序单链表，我们可以采用以下步骤：
-
初始化一个新的链表头：创建一个哑节点
dummy，它将帮助我们简化链表的操作，并最终返回它的下一个结点作为合并后的链表头。 -
逐步比较两个链表的结点：
- 比较两个链表当前结点的值，将较小的值添加到新链表中。
- 移动指针，使得每次比较之后，较小值的链表向后移动一个结点。
-
处理剩余的结点：
- 如果其中一个链表先为空，则将另一个链表剩余的所有结点直接链接到新链表的末尾。
-
返回合并后的链表：返回哑节点的下一个结点作为合并后链表的头结点。
5. 实现代码
5.1 关键函数实现
#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* head1, struct ListNode* head2) {
// 创建一个哑节点，便于处理头节点
struct ListNode* dummy = createNode(-1);
struct ListNode* curr = dummy; // 新链表的当前指针
// 逐步比较两个链表的结点
while (head1 != NULL && head2 != NULL) {
if (head1->val <= head2->val) {
curr->next = head1;
head1 = head1->next;
} else {
curr->next = head2;
head2 = head2->next;
}
curr = curr->next; // 移动到新链表的下一个位置
}
// 将剩余的结点直接链接到新链表末尾
if (head1 != NULL) {
curr->next = head1;
} else {
curr->next = head2;
}
// 返回合并后的链表（跳过哑节点）
struct ListNode* mergedHead = dummy->next;
free(dummy);
return mergedHead;
}
// 打印链表
void printList(struct ListNode* head) {
while (head != NULL) {
printf("%d -> ", head->val);
head = head->next;
}
printf("NULL\n");
}
5.2 模拟过程
假设我们有两个链表：
- 链表1：1 -> 3 -> 5
- 链表2：2 -> 4 -> 6
Step 1：初始化哑节点 dummy，curr指向dummy。
Step 2：比较链表1和链表2的第一个结点，1 <= 2，将1添加到新链表。
Step 3：比较链表1和链表2的下一个结点，3 > 2，将2添加到新链表。
重复这个过程，直到处理完两个链表中的所有结点。
最终合并的链表为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
5.3 完整 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* head1, struct ListNode* head2) {
struct ListNode* dummy = createNode(-1);
struct ListNode* curr = dummy;
while (head1 != NULL && head2 != NULL) {
if (head1->val <= head2->val) {
curr->next = head1;
head1 = head1->next;
} else {
curr->next = head2;
head2 = head2->next;
}
curr = curr->next;
}
if (head1 != NULL) {
curr->next = head1;
} else {
curr->next = head2;
}
struct ListNode* mergedHead = dummy->next;
free(dummy);
return mergedHead;
}
// 打印链表
void printList(struct ListNode* head) {
while (head != NULL) {
printf("%d -> ", head->val);
head = head->next;
}
printf("NULL\n");
}
int main() {
// 创建链表1：1 -> 3 -> 5
struct ListNode* list1 = createNode(1);
list1->next = createNode(3);
list1->next->next = createNode(5);
// 创建链表2：2 -> 4 -> 6
struct ListNode* list2 = createNode(2);
list2->next = createNode(4);
list2->next->next = createNode(6);
printf("链表1：\n");
printList(list1);
printf("链表2：\n");
printList(list2);
// 合并链表
struct ListNode* mergedList = mergeTwoLists(list1, list2);
printf("合并后的链表：\n");
printList(mergedList);
return 0;
}
5.4 代码说明
- createNode：创建一个新的链表结点。
- mergeTwoLists：将两个有序链表合并为一个新的有序链表，并返回合并后的链表头。
- printList：打印链表内容。
6. 时间和空间复杂度分析
- 时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度。因为我们需要遍历两个链表的所有结点进行合并。
- 空间复杂度：O(1)，因为我们只使用了常数级别的额外空间（不包括输入链表的存储空间）。
7. 总结
通过该算法，我们能够高效地将两个有序单链表合并为一个新的有序链表。该算法的核心是通过逐步比较两个链表的当前结点，维护一个合并后的链表。
