力扣算法题-23.合并K个升序链表 C语言实现

题目

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

示例 2： 输入：lists = [] 输出：[]

示例 3： 输入：lists = [[]] 输出：[]

提示： k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

思路

1、每次循环添加一个节点，并将添加节点所在的链表移位，赋值到数组中； 2、每次循环中遍历数组，寻找最小值所在的节点，即为添加节点；

程序

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){ int i, Min, iMin, izcnt = 0,iflag = 1; struct ListNode* head = NULL; struct ListNode* node = NULL; /*判断链表是否都为空*/ iflag = 0; for(i=0;i<listsSize;i++){ if(lists[i] != NULL){ iflag = 1; }else{ izcnt++; } } while(iflag){ /*获取最小值的初始值*/ for(i=0;i<listsSize;i++){ if(lists[i] != NULL){ Min = lists[i]->val; iMin = i; break; } } /*获取最小值和最小序列*/ for(i=i+1;i<listsSize;i++){ if(lists[i] != NULL){ iMin = Min > lists[i]->val ? i : iMin; Min = Min > lists[i]->val ? lists[i]->val : Min; } } /*连接链表*/ if(head == NULL){ head = lists[iMin]; node = head; }else{ node->next = lists[iMin]; node = node->next; } /*移动链表*/ lists[iMin] = lists[iMin]->next; /*记录空链表个数，全部为空时，停止循环*/ if(lists[iMin] == NULL){ izcnt++; if(izcnt == listsSize){ iflag = 0; } } } return head; }