利用编程思维做题之将两个有序的单链表合并成一个新的有序单链表

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;
}