#include <stdio.h> #include <stdlib.h> //定义链表结点 typedef struct ListNode { int val; struct ListNode* next; }ListNode; void ListAdd(ListNode** tail, ListNode* node) { (*tail)->next = node; *tail = node; } //合并2个有序链表 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { //判断是需要进行排序 if (!list1) { return list2; } if (!list2) { return list1; } //创建一个新链表,并初始化head、tail为NULL ListNode* head = NULL; ListNode* tail = NULL; //遍历2个链表,同时进行比较,将val较小的结点连接至新链表中 while (list1 && list2) { if (list1->val > list2->val) { //将list2链接至新链表 if (head == NULL) { head = tail = list2; } else { ListAdd(&tail, list2); } list2 = list2->next; } else { //将list1链接至新链表 if (head == NULL) { head = tail = list1; } else { ListAdd(&tail, list1); } list1 = list1->next; } } //链接剩余结点 if (!list1) { //链接list2 ListAdd(&tail, list2); } else { //链接list1 ListAdd(&tail, list1); } return head; } //创建新结点,返回新结点地址 ListNode* ListBuyNode(int x) { //创建新结点 ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); if (!newNode) { perror("malloc fail!"); exit(1); } newNode->val = x; newNode->next = NULL; return newNode; } //打印链表 void ListPrint(ListNode* phead) { //判断是否需要打印,以免后续解引用时造成越界访问 if (phead == NULL) { return; } ListNode* pcur = phead; while (pcur != NULL) { printf("%d ", pcur->val); pcur = pcur->next; } } //释放链表 void ListFree(ListNode* phead) { //判断是否有结点以供释放 if (phead) { return; } ListNode* pcur = phead; ListNode* prev = NULL; while (pcur != NULL) { prev = pcur; pcur = pcur->next; free(prev); } } int main() { ListNode* head1 = NULL; ListNode* head2 = NULL; ListNode* tail1 = NULL; ListNode* tail2 = NULL; ListNode* mergeHead = NULL; int input = 0; char judge = 0; //录入链表1 judge = 1; while (judge != '\n') { scanf("%d", &input); judge = getchar(); if (head1 == NULL) { //链表为空时,同时更新头结点指针 head1 = tail1 = ListBuyNode(input); } else { //链表不为空,只更新尾结点指针即可 tail1->next = ListBuyNode(input); tail1 = tail1->next; } } //录入链表2 judge = 1; while (judge != '\n') { scanf("%d", &input); judge = getchar(); if (head2 == NULL) { //链表为空时,同时更新头结点指针 head2 = tail2 = ListBuyNode(input); } else { //链表不为空,只更新尾结点指针即可 tail2->next = ListBuyNode(input); tail2 = tail2->next; } } //合并链表 mergeHead = mergeTwoLists(head1, head2); //打印链表 ListPrint(mergeHead); //释放链表 ListFree(mergeHead); return 0; }