面试题目：(2)合并多个升序链表

题目

按固定格式输入多个已经排好升序的链表，合并成一个链表输出

输入

[[1,4,5],
[2,3,6],
[1,4]]

输出

[1,1,2,3,4,4,5,6]

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*合并字符串链表输入[[1,4,5],[2,3,6],[1,4]]输出[1,1,2,3,4,4,5,6]
*/
struct ListNode {int val;struct ListNode *next;
};// 合并两个已排序的链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if (!l1) return l2;if (!l2) return l1;if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}
}// 合并K个链表的函数
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (listsSize == 0) return NULL;if (listsSize == 1) return lists[0];int mid = listsSize / 2;struct ListNode *left = mergeKLists(lists, mid);struct ListNode *right = mergeKLists(lists + mid, listsSize - mid);return mergeTwoLists(left, right);
}// 创建一个新节点
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 打印链表
void printList(struct ListNode* head) {printf("[");while (head != NULL) {printf("%d", head->val);head = head->next;if (head != NULL){printf(",");}}printf("]");printf("\n");
}int main() {char s2[256]= "";int list_count = 0;while (1){char s1[256]= "";fgets(s1,sizeof(s1),stdin);// 去除可能存在的换行符size_t len = strlen(s1);if (len > 0 && s1[len-1] == '\n') {s1[len-1] = '\0';  // 去掉换行符len--;  // 更新字符串长度}list_count++;// 检查最后一个字符是否是逗号if (len > 0 && s1[len-1] == ',') {s1[len-1] = '!';  // 去掉换行符strcat(s2,s1);} else {strcat(s2,s1);break;}}size_t len = strlen(s2);s2[len-1]='!';//printf("合并后的字符串: %d\n", list_count);//printf("合并后的字符串: %s\n", s2);struct ListNode* lists[list_count];  // 创建存储链表头指针的数组int k = 0;struct ListNode* head = NULL;struct ListNode* tail = NULL;for (int i = 0; s2[i] != '\0'; i++) {if (s2[i] == '!'){lists[k++] = head;head = NULL;tail = NULL;}else if (s2[i] >= '0' && s2[i] <= '9'){int value = s2[i] - '0';//printf("%d",value);struct ListNode* newNode = createNode(value);if (head == NULL) {head = newNode;tail = newNode;} else {tail->next = newNode;tail = newNode;}}}// for (int i = 0; i <= list_count-1; i++)// {//     printList(lists[i]);// }// 合并所有链表并打印结果struct ListNode* mergedList = mergeKLists(lists, k);printf("合并后的链表: ");printList(mergedList);return 0;
}

步骤

获取输入的链表字符串，并记录多少条链表
按格式修改字符串，并获取每条链表中的元素
新建链表数组，存放每条链表的值
合并多个链表
- 从中间分开左右，直到分到两个数组为止，然后就合并两个数组
- 拿合并完的数组根右边的数组再合并
- 最终合并为一个链表
- 输出

输入字符串解析

一行一行获取，获取了一行判断最后一位字符是不是"["
- 不是就继续获取，并将最后一个字符改为“!”
  - “!”为一个链表的结束
- 是就退出
获取最后都添加到一个字符串里
并将最后的字符改为“!”
判断字符串里的数字，直到！为一个链表结束

多个链表合并解析

有1，2，3，4，5，6，7个链表
从中间分开，7/2=3，左边left1三个1，2，3，右边right1四个4，5，6，7
- 左边继续分，3/2=1，左边left2一个1，右边right2俩个2，3（合并为right3）
- 然后left2和right3合并为end_left
右边right1也是如此，最终右边right1也会最终合并为一个end_right
最后让end_left和end_right合并就为最终的链表