实现合并两个有序的单链表

要合并两个有序的单链表，你可以创建一个新的节点作为头结点，并遍历两个链表。在遍历过程中，比较当前节点的值，选择较小的一个添加到新链表并移动指针。当其中一个链表遍历完时，只需将另一个链表剩余的部分连接到新链表的尾部即可。
以下是一个简单的C语言实现：
#include <stdio.h>
#include <stdlib.h>

// 定义链表结构体
typedef struct Node {
int data;
struct Node* next;
} Node;

// 创建新链表节点
Node* createNode(int val) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode != NULL) {
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}

// 合并两个有序链表
Node* mergeSortedLists(Node* list1, Node* list2) {
// 新链表头结点
Node* head = NULL;
// 当前节点指针
Node* curr = head;

// 遍历链表
while (list1 &amp;&amp; list2) {
// 比较节点值
if (list1->data <= list2->data) {
// 将较小节点添加到新链表
curr->next = list1;
list1 = list1->next;
} else {
curr->next = list2;
list2 = list2->next;
}
// 移动新链表指针
curr = curr->next;
}

// 如果其中一个链表未遍历完，将其余部分添加到新链表尾部
if (list1) {
curr->next = list1;
} else {
curr->next = list2;
}

return head;
}

// 打印链表
void printList(Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}

int main() {
Node* list1 = createNode(1); // [1]
list1->next = createNode(3); // [1, 3]
list1->next->next = createNode(5);

Node* list2 = createNode(2); // [2]
list2->next = createNode(4); // [2, 4]
list2->next->next = createNode(6);

Node* mergedList = mergeSortedLists(list1, list2); // 合并后 [1, 2, 3, 4, 5, 6]

printList(mergedList); // 输出结果

return 0;
}
登录后复制