合并两个有序的单链表C语言 合并两个有序的单链表C语言 合并两个有序的单链表的自定义函数C语言

在C语言中，合并两个有序的单链表通常会定义一个名为`mergeTwoLists`的自定义函数，它接受两个链表的头结点作为输入参数，返回合并后的新链表头结点。下面是一个简单的实现示例： ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 typedef struct ListNode { int val; // 节点值 struct ListNode* next; // 指向下一个节点的指针 } ListNode; // 助手函数，用于打印链表 void printList(ListNode* head) { ListNode* temp = head; while (temp != NULL) { printf("%d ", temp->val); temp = temp->next; } printf("\n"); } // 自定义函数合并两个有序链表 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // 初始情况：如果其中一个链表为空，则返回另一个 if (l1 == NULL) return l2; if (l2 == NULL) return l1; // 使用三指针技巧，合并两个链表 ListNode* dummy = (ListNode*)malloc(sizeof(ListNode)); // 创建虚拟头节点 dummy->next = l1; ListNode* tail = dummy; ListNode* iter1 = l1; ListNode* iter2 = l2; while (iter1 && iter2) { if (iter1->val <= iter2->val) { tail->next = iter1; iter1 = iter1->next; } else { tail->next = iter2; iter2 = iter2->next; } tail = tail->next; } // 把剩余的链表添加到结果中 tail->next = (iter1 ? iter1 : iter2); return dummy->next; // 返回合并后的新链表头节点 } int main() { // 测试示例 ListNode* list1 = createLinkedList(1, 3, 5); ListNode* list2 = createLinkedList(2, 4, 6); ListNode* mergedList = mergeTwoLists(list1, list2); printList(mergedList); // 输出：1 2 3 4 5 6 return 0; } // 辅助函数，创建给定值的链表 ListNode* createLinkedList(int* values, int length) { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); head->val = values[0]; head->next = NULL; for (int i = 1; i < length; i++) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->val = values[i]; newNode->next = head->next; head->next = newNode; } return head; } ``` 这个例子中，`main`函数创建了两个已排序的链表，然后调用`mergeTwoLists`函数合并它们，并打印出结果。