Merge k Sorted Lists

Description:

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Example:

Given lists:

[
     2->4->null,
     null,
     -1->null
]

return -1->2->4->null.

分析：

和Find Minimum in Rotated Sorted Array II基本一样。

注意：

  1. 当进行“分而治之”的二分查找时，终止条件是当只有两个元素时才进行merge操作。
  2. 注意 37行 的 end = middle - 1 ，38行 的 start = middle ，这样做就可以避免出现 start > end 的情况（这里的 start 和 end 指的是传递的实际的参数值，而不是特指某一个值）。

思路：

  1. 如果 lists.size() == 1 ，直接返回。
  2. 如果 lists.size() > 1 ，进行“分而治之”的二分查找
    • 如果 end - start == 1 ，此时只有两个元素，可以直接进行merge。
    • 如果 end - start == 1 ，需要再次进行二分，得到左边和右边的各自merge好的linked list：left 和 right ，然后对两者进行merge。
    • 如果不是上面两种情况，说明 start == end ，直接返回即可
  3. 否则直接返回 nullptr （注意这里，此时就是 lists.size() == 0 的情况，如果在开头把它当作一种情况，函数就没有值可以返回了。也就是说当不知道函数返回什么的时候，可以把一种情况做返回值）。

Code:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        if (lists.size() == 1) return lists[0];
        
        if (lists.size() > 1) {
            return binaryMerge(lists, 0, lists.size() - 1);
        }
        
        return nullptr;
    }
    
    ListNode *binaryMerge(vector<ListNode *> &lists, int start, int end) {
        if (end - start == 1) {
            return mergeOperation(lists[start], lists[end]);
        }
        
        if (end - start > 1) {
            int middle = (end - start) / 2 + start;
            ListNode *left = binaryMerge(lists, start, middle - 1);
            ListNode *right = binaryMerge(lists, middle, end);
            return mergeOperation(left, right);
        }
        
        return lists[start]; //start == end
    }
    
    ListNode *mergeOperation(ListNode *left, ListNode *right) {
        if (left == nullptr) return right;
        if (right == nullptr) return left;
        
        ListNode *head = new ListNode(INT_MIN);
        ListNode *curr = head;
        
        while (left != nullptr && right != nullptr) {
            if (left->val < right->val) {
                curr->next = new ListNode(left->val);
                curr = curr->next;
                left = left->next;
            }
            else {
                curr->next = new ListNode(right->val);
                curr = curr->next;
                right = right->next;
            }
        }
        
        while (left != nullptr) {
            curr->next = new ListNode(left->val);
            curr = curr->next;
            left = left->next;
        }
        
        while (right != nullptr) {
            curr->next = new ListNode(right->val);
            curr = curr->next;
            right = right->next;
        }
        
        return head->next;
    }
};