https://leetcode.com/problems/merge-k-sorted-lists/

1. Use Divide and Conquer(two pointers):

  1. //24 ms    12.2 MB
  3. /**
  4.  * Definition for singly-linked list.
  5.  * struct ListNode {
  6.  *     int val;
  7.  *     ListNode *next;
  8.  *     ListNode() : val(0), next(nullptr) {}
  9.  *     ListNode(int x) : val(x), next(nullptr) {}
  10.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  16.         if(lists.size()==0) return NULL;
  17.         if(lists.size()==1) return lists[0];
  19.         int n = lists.size();
  20.         int last = n - 1;
  22.         int l = 0;
  23.         int r = last;
  25.         while(l < r){
  26.             lists[l] = mergeTwoLists(lists[l], lists[r]);
  27.             l++;
  28.             r--;
  30.             if(l>=r){
  31.                 last = r;
  32.                 l = 0;
  33.                 r = last;
  34.             }
  35.         }
  36.         return lists[0];
  37.     }
  39. private:
  40.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  41.         ListNode* dummy = new ListNode();
  42.         ListNode* curr = dummy;
  44.         while(l1 && l2){
  45.             if(l1->val < l2->val){
  46.                 curr->next = l1;
  47.                 l1 = l1->next;
  48.             } else {
  49.                 curr->next = l2;
  50.                 l2 = l2->next;
  51.             }
  52.             curr = curr->next;
  53.         }
  55.         ListNode* rest = l1 ? l1 : l2;
  57.         if(rest)
  58.             curr->next = rest;
  60.         return dummy->next;
  61.     }
  62. };