Cinte's Leetcode Record
0%

23. Merge k Sorted Lists

Posted on Edited on In Disqus:
Symbols count in article: 6.9k Reading time ≈ 6 mins.

23. Merge k Sorted Lists

Solution 1

思路 

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
/**
 * 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.empty()) return nullptr;
        vector<ListNode*> newLists;   
        for(size_t i = 0; i < lists.size(); i = i + 2)
        {
            if(i != lists.size() - 1)
            {
                newLists.push_back(mergeTwoLists(lists[i], lists[i + 1]));
            }else
            {
                newLists.push_back(lists[i]);
            }
        }
        if(newLists.size() == 1)
            return newLists[0];
        
        return mergeKLists(newLists);
    }
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        if(!l1) return l2;
        if(!l2) return l1;
        while(l1 && l2)
        {
            if(l1->val > l2->val)
            {
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }else
            {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            }
        }
        return nullptr;
    }
};
Time complexity: O(NlogK)
Space complexity: O(logK)

优化后 

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
/**
 * 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) {
        int stride = 1;
        int sz = lists.size();
        while(stride < sz)
        {
            for(size_t i = 0; i < sz - stride; i = i + 2 * stride)
            {
                lists[i] = mergeTwoLists(lists[i], lists[i + stride]);
            }
            stride *= 2;
        }   
        return lists.empty() ? nullptr : lists[0];
    }
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        if(!l1) return l2;
        if(!l2) return l1;
        while(l1 && l2)
        {
            if(l1->val > l2->val)
            {
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }else
            {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            }
        }
        return nullptr;
    }
};
Time complexity: O(NlogK)
Space complexity: O(1)

review
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
/**
 * 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) {
        for(int step = 1; step < lists.size(); step *= 2)
        {
            for(int i = 0; i < lists.size() - step; i += 2 * step)
                lists[i] = merge(lists[i], lists[i + step]);
        }
        return lists.empty() ? nullptr : lists[0];
    }
private:
    ListNode* merge(ListNode* l1, ListNode* l2)
    {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        
        if(l1->val > l2->val)
        {
            l2->next = merge(l1, l2->next);
            return l2;
        }else
        {
            l1->next = merge(l1->next, l2);
            return l1;
        }
        return nullptr;
    }
};
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
/**
 * 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.empty())
            return nullptr;
        int n = lists.size();
        for(int stride = 1; stride < n; stride *= 2)  // 这里是为了可以是最前面和最后面归并，如果是奇数，会最后第一个和最后一个一起归，如果是偶数，那就不用了
        {
            for(int i = 0; i < n - stride; i += stride * 2) // (注意这个n-stride十分重要，因为最后一步中i的位置是位于n-sride-1,所以需要让i停下来)(可能并不重要？因为我后面不用也可以)我后面不用是因为我进行了判断
                lists[i] = merge(lists[i], lists[i + stride]);
        }
        return lists[0];
    }
private:
    ListNode* merge(ListNode* l1, ListNode* l2)
    {
        ListNode ret;
        ListNode* pseudoHead = &ret;
        while(l2 && l1)
        {
            if(l1->val < l2->val)
            {
                pseudoHead->next = l1;
                l1 = l1->next;
            }
            else
            {
                pseudoHead->next = l2;
                l2 = l2->next;
            }
            pseudoHead = pseudoHead->next;
        }
        pseudoHead->next = l1 ? l1 : l2;
        return ret.next;
    }
};
再次review
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
/**
 * 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.empty())
            return nullptr;
        int n = lists.size();
        for(int step = 1; step < n; step *= 2)
            for(int i = 0; i < n; i += step * 2)
                lists[i] = merge(lists[i], i + step < n ? lists[i + step] : nullptr); //这里我进行了判断，所以不用担心超出了范围
        return lists[0];
    }
private:
    ListNode* merge(ListNode* l1, ListNode* l2)
    {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        if(l1->val < l2->val)
        {
            l1->next = merge(l1->next, l2);
            return l1;
        }else
        {
            l2->next = merge(l2->next, l1);
            return l2;
        }
        return nullptr;
    }
};
Solution 2 use priority_queue
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
/**
 * 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 cuscomp
{
public:
    bool operator()(pair<int, ListNode *> p1, pair<int, ListNode *> p2)
    {
        return p1.first > p2.first;
    }
};
class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        std::priority_queue<pair<int, ListNode *>, std::vector<pair<int, ListNode *>>, cuscomp> q;
        ListNode *point = new ListNode();
        ListNode *head = point;
        for (auto &list : lists)
        {
            if(list)
                q.push(make_pair(list->val, list));
        }
        while (!q.empty())
        {
            auto node = q.top().second;
            q.pop();
            point->next = new ListNode(node->val);
            point = point->next;
            node = node->next;
            if (node)
                q.push(make_pair(node->val, node));
        }
        return head->next;
    }
};
review
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
/**
 * 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) {
        priority_queue<ListNode*, vector<ListNode*>, cusComp> pq;
        ListNode* pesudoHead = new ListNode();
        ListNode* point = pesudoHead;
        for(auto& node : lists)
            if(node)
                pq.push(node);
        while(!pq.empty())
        {
            auto p = pq.top();
            pq.pop();
            point->next = p;
            point = point->next;
            if(p->next)
                pq.push(p->next);
        }
        return pesudoHead->next;
    }
private:
    class cusComp
    {
    public:
        bool operator()(ListNode* p1, ListNode* p2)
        {
            return p1->val > p2->val;
        }
    };
};

Time complexity: O(NlogK)
Space complexity: O(N)