---
tags: LeetCode,Top 100 Liked Questions
---
# 23. Merge k Sorted Lists
https://leetcode.com/problems/merge-k-sorted-lists/submissions/
## 題目敘述
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.
## Example
Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

## 解題想法
### 1.Divide And Conquer
利用Divide And Conquer將原本問題變成2個Sorted Lists的merge
並在每次merge完將後面的list刪去
最後當array中只有1個list時即得解

class Solution {
public:
    ListNode* mergenodes(ListNode* l1,ListNode* l2) {
        ListNode* sorted_node=NULL;
        if(l1==NULL){
            return l2;
        }
        else if(l2==NULL){
            return l1;
        }
        if(l1->val < l2->val){
            sorted_node=l1;
            sorted_node->next= mergenodes(l1->next,l2);
        }
        else{
            sorted_node=l2;
            sorted_node->next=mergenodes(l1,l2->next);
        }
        return sorted_node;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()<1){
            return NULL;
        }
        int i=0;
        int j=lists.size()-1;
        while(j>0){
            i=0;
            j=lists.size()-1;
            while(i<j){
                lists[i]=mergenodes(lists[i],lists[j]);
                i++;
                lists.pop_back();
                j=lists.size()-1;
            }
        }
        return lists[0];
    }
};

時間複雜度為O(N log N)