23. Merge k Sorted Lists

A typical divide and conquer solution. We need to find the correct termination condition. I use "if (lo > hi) return NULL" as termination condition but got run time error. We should terminate at two conditions:
1. lo == hi, return lists[lo]
2. lo+1 == hi, merge lists[lo] and lists[hi] and return.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* mergeKLists(vector<ListNode*>& lists) {  
12:      if (lists.size() == 0) return NULL;  
13:      if (lists.size() == 1) return lists[0];  
14:      return sortLists(lists, 0, (int)lists.size()-1);  
15:    }  
16:    ListNode *sortLists(vector<ListNode*> &lists, int lo, int hi) {  
17:      if (lo == hi) return lists[lo];  
18:      if (lo+1 == hi) return merge(lists[lo], lists[hi]);  
19:      int mid = lo + (hi - lo) / 2;  
20:      ListNode *l1 = sortLists(lists, lo, mid-1);  
21:      ListNode *l2 = sortLists(lists, mid, hi);  
22:      return merge(l1, l2);  
23:    }  
24:    ListNode *merge(ListNode *l1, ListNode *l2) {  
25:      ListNode *dummy = new ListNode(-1);  
26:      ListNode *cur = dummy;  
27:      while (l1 && l2) {  
28:        if (l1->val < l2->val) {  
29:          cur->next = l1;  
30:          l1 = l1->next;  
31:        } else {  
32:          cur->next = l2;  
33:          l2 = l2->next;  
34:        }  
35:        cur = cur->next;  
36:      }  
37:      if (l1) cur->next = l1;  
38:      if (l2) cur->next = l2;  
39:      cur = dummy->next;  
40:      delete dummy;  
41:      return cur;  
42:    }  
43:  };  

When I revisited this problem, the terminal condition can be simplified to:
1. s == e, return lists[s]; 2. s > e, return NULL.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* mergeKLists(vector<ListNode*>& lists) {  
12:      return helper(lists, 0, lists.size()-1);  
13:    }  
14:    ListNode *helper(vector<ListNode*> &lists, int s, int e) {  
15:      if (s == e) return lists[s];  
16:      if (s > e) return NULL;  
17:      int mid = s + (e - s) / 2;  
18:      ListNode *l1 = helper(lists, s, mid);  
19:      ListNode *l2 = helper(lists, mid+1, e);  
20:      ListNode *dummy = new ListNode(-1);  
21:      ListNode *cur = dummy;  
22:      while (l1 && l2) {  
23:         if (l1->val < l2->val) {  
24:           cur->next = l1;  
25:           l1 = l1->next;  
26:         } else {  
27:           cur->next = l2;  
28:           l2 = l2->next;  
29:         }  
30:         cur = cur->next;  
31:      }  
32:      if (l1) cur->next = l1;  
33:      if (l2) cur->next = l2;  
34:      cur = dummy->next;  
35:      delete dummy;  
36:      return cur;  
37:    }  
38:  };