LeetCode - 23. Merge k Sorted Lists

23. Merge k Sorted Lists 

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

将k个有序链表合并为一个有序链表.

analyse:

方法一：本着不重复发明*的原则，使用两两合并，就可以利用前面已经做过的Merge two Sorted Lists.

方法二：抖机灵.将所有结点的val都push_back在一个vector容器中，排序后又重新构造链表.

Time complexity: O(N)

 

view code

方法一：

ListNode * mergeKLists( vector < ListNode *> & lists) {
    if( lists . empty ()){
        return nullptr;
    }
    while( lists . size() > 1 ){
        lists . push_back( mergeTwoLists( lists [ 0 ], lists [ 1 ]));
        lists . erase( lists . begin());
        lists . erase( lists . begin());
    }
    return lists . front();
}
ListNode * mergeTwoLists( ListNode * l1 , ListNode * l2) {
    if( l1 == nullptr ){
        return l2;
    }
    if( l2 == nullptr ){
        return l1;
    }
    if( l1 -> val <= l2 -> val ){
        l1 -> next = mergeTwoLists( l1 -> next , l2);
        return l1;
    }
    else {
        l2 -> next = mergeTwoLists( l1 , l2 -> next);
        return l2;
    }
}

方法二：

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-02-18-09.02
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode * next;
    ListNode( int x) : val( x ), next( NULL) {}
};

class Solution
{
public :
    ListNode * mergeKLists( vector < ListNode *>& lists)
    {
        vector < int > nodeVal;
        for( auto ptr: lists)
        {
            while( ptr)
            {
                nodeVal . push_back( ptr -> val);
                ptr = ptr -> next;
            }
        }
        if( nodeVal . size() <= 0)
        {
            return nullptr;
        }

        sort( nodeVal . begin (), nodeVal . end());
        bool isFirst = 1;
        ListNode * res = nullptr , * head = nullptr;
        for( auto p: nodeVal)
        {
            if( isFirst)
            {
                isFirst = 0;
                head = new ListNode(p);
                res = head;
            }
            else
            {
                head -> next = new ListNode(p);
                head = head -> next;
            }
        }
        return res;
    }
};

ListNode * getList( vector < int >& arr)
{
    bool isFirst = 1;
    ListNode * res = nullptr , * head = nullptr;
    for( auto p: arr)
    {
        if( isFirst)
        {
            isFirst = 0;
            head = new ListNode(p);
            res = head;
        }
        else
        {
            head -> next = new ListNode(p);
            head = head -> next;
        }
    }
    return res;
}

int main()
{
    Solution solution;
    int n;
    while( cin >>n)
    {
        vector < ListNode *> listVe;
        while(n --)
        {
            int num;
            cin >> num;
            vector < int > ve;
            for( int i = 0; i < num; ++ i)
            {
                int tmp;
                cin >> tmp;
                ve . push_back( tmp);
            }
            listVe . push_back( getList( ve));
        }
        ListNode * head = solution . mergeKLists( listVe);
        while( head)
        {
            cout << head -> val << " ";
            head = head -> next;
        }
        cout << "End." << endl;
    }
    return 0;
}
/*

*/