引言
题目链接：https://leetcode.com/problems/merge-k-sorted-lists/description/
题目大意
合并k个已排序的链表并将其作为一个排序列表返回。 分析并描述其复杂性。
- Example
|
1 2 3 4 5 6 7 |
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 |
题解
一句话题解：直接借用21题 Merge Two Sorted Lists 的双链表合并借用归并排序的思想分治合并即可
复杂度
时间复杂度 O(nlogn)
空间复杂度 O(1)
AC代码
c++版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { int n = lists.size(); if (0 == n) { return nullptr; } while (n > 1) { int mid = (n + 1) >> 1; for (int i = 0; i < (n >> 1); ++i) { lists[i] = mergeTwoLists(lists[i], lists[i + mid]); } n = mid; } return lists[0]; } private: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *pRet = new ListNode(0); ListNode *curNode = pRet; while (nullptr != l1 && nullptr != l2) { if (l1->val < l2->val) { curNode->next = l1; l1 = l1->next; } else { curNode->next = l2; l2 = l2->next; } curNode = curNode->next; } curNode->next = nullptr == l1 ? l2 : l1; return pRet->next; } }; |
go版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { pRet := &ListNode{0, nil} curNode := pRet for nil != l1 && nil != l2 { if l1.Val < l2.Val { curNode.Next = l1 l1 = l1.Next } else { curNode.Next = l2 l2 = l2.Next } curNode = curNode.Next } if nil != l1 { curNode.Next = l1 } else { curNode.Next = l2 } return pRet.Next } func mergeKLists(lists []*ListNode) *ListNode { n := len(lists) if 0 == n { return nil } for n > 1 { mid := (n + 1) >> 1 for i := 0; i < (n >> 1); i++ { lists[i] = mergeTwoLists(lists[i], lists[i+mid]) } n = mid } return lists[0] } |
