###### tags: `LeetCode` `Linked List` `Merge Sort` `Hard`
# LeetCode #23 [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
### (Hard)

給你一個鏈結串列數組，每個鏈結串列都已經按升序排列。

請你將所有鏈結串列合併到一個升序鏈結串列中，返回合併後的鏈結串列。

---

一次處理兩個鏈結串列的merge sort, 並將處理完的鏈結串列存入鏈結串列數組中, 再刪掉處理過的鏈結串列(數組中的前兩個), 直到整個數組只剩下一個鏈結串列時, 返回該鏈結串列即可。

---

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(!lists.size())return nullptr;
        while(lists.size()>1){
            lists.push_back(mergeTwo(lists[0], lists[1]));
            lists.erase(lists.begin());
            lists.erase(lists.begin());
        }
        return lists.front();
    }
    ListNode* mergeTwo(ListNode* l1, ListNode* l2){
        if(!l1)return l2;
        else if(!l2)return l1;
        else if(l1->val<=l2->val){
            l1->next = mergeTwo(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwo(l1, l2->next);
            return l2;
        }
    }
};