您现在的位置是：亿华云 > 应用开发

leetcode23. 合并K个排序链表

亿华云2025-10-03 06:40:36【应用开发】1人已围观

简介1. 题目描述合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入:[1->4->5,1->3->4,2->6]输出:1->1->

1. 题目描述

合并 k 个排序链表，合并返回合并后的排序排序链表。请分析和描述算法的链表复杂度。示例:输入:[1->4->5,合并1->3->4,2->6]输出:1->1->2->3->4->4->5->6来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

2. 解题思路

/*解题思路：解法一、云服务器顺序合并1、排序lists[0]与lists[1]合并，链表结果与lists[2]合并...结果与lists[listsSize-1]合并解法二、合并分治合并1、排序lists[0]与lists[1]合并,链表lists[2]与lists[3]合并,然后将合并的服务器租用结果继续合并。*/

3. 测试结果

解法一、合并顺序合并

解法二、排序分治合并

4. 顺序合并

/*title: leetcode23. 合并K个排序链表author: xidoublestarmethod: 顺序合并type: Cdate: 2020-5-27*/structListNode* mergeTwoLists(structListNode* l1,链表structListNode* l2){ if(!l1)return l2;if(!l2)return l1;structListNode* head =(structListNode*)malloc(sizeof(structListNode)),* tail = head;while(l1 && l2){ if(l1->val < l2->val){ tail->next = l1; l1 = l1->next;}else{ tail->next = l2; l2 = l2->next;} tail = tail->next;}if(l1) tail->next = l1;elseif(l2) tail->next = l2; tail = head; head = head->next; free(tail);return head;}structListNode* mergeKLists(structListNode** lists,int listsSize){ if(listsSize ==0)return NULL;structListNode* res =*lists;for(int i =1; i < listsSize; i++){ if(lists[i]!= NULL) res = mergeTwoLists(res, lists[i]);}return res;}

5. 分治合并

/*title: leetcode23. 合并K个排序链表author: xidoublestarmethod: 顺序合并type: Cdate: 2020-5-27*/structListNode* mergeTwoLists(structListNode* l1,structListNode* l2){ if((!l1)||(!l2))return l1 ? l1 : l2;structListNode head; head.next = NULL;structListNode* tail =&head;while(l1 && l2){ if(l1->val < l2->val){ tail->next = l1; l1 = l1->next;}else{ tail->next = l2; l2 = l2->next;} tail = tail->next;} tail->next = l1 ? l1 : l2;return head.next;}structListNode* merge(structListNode** lists,int left,int right){ if(left == right)return lists[left];if(left > right)return NULL;int mid =(left + right)>>1;structListNode* p1 = merge(lists, left, mid);structListNode* p2 = merge(lists, mid +1, right);return mergeTwoLists(p1, p2);}structListNode* mergeKLists(structListNode** lists,int listsSize){ if(listsSize ==0)return NULL;return merge(lists,0, listsSize -1);}