leetcode23. 合并K个排序链表-IT技术-益华网络-网站建设_小程序开发|网页设计

leetcode23. 合并K个排序链表

发布时间：2025-05-23 11:09:01 作者：益华网络来源：undefined 浏览量（0）点赞（0）

摘要：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-list

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);}