题目描述

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

思路有很多

1.先将这些链表转化为一个vector int型的数组，然后排序后，再转化为链表。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *mergeKLists(vector
      
        &lists) {        ListNode* res=new ListNode(-1);        ListNode* res_tmp=res;                vector
       
         A;        for(int i=0;i
        
         val);                lists[i]=lists[i]->next;            }        }        for(int m=0;m
         
          A[n]){                    int temp=A[n];                    A[n]=A[m];                    A[m]=temp;                }            }            ListNode* tmp=new ListNode(A[m]);            res_tmp->next=tmp;            res_tmp=res_tmp->next;        }                return res->next;                                                            }};
         
        
       
      

2.利用STL中的heap。heap有很多排序的方法。

首先新建一个vector<ListNode *> 类型的变量，然后先将这些lists放入这个新建的链表容器中。

将该链表容器转化为heap（堆）：利用make_heap

STL提供的是max-heap也就是从大到小排列，因此要改到从小到大排列。然后将第一个和最后一个调换，再输出最后一个，放入新的链表即可：

static bool compareLess(ListNode* l1,ListNode* l2)   {       return l1->val > l2->val;   }   ListNode* mergeKLists(vector
      
        &lists)   {      ListNode fake(0);      ListNode *cur = &fake;      vector
       
         vec;             int listSize = lists.size();      for(int i=0;i
        
         next = vec.front();                       // 堆第一个节点first为最小值节点          pop_heap(vec.begin(),vec.end(),compareLess);   // 它把first和last-1交换，然后重新生成一个堆          vec.pop_back();                                // 容器弹出最后一个节点          cur = cur->next;          if(cur->next)                                  // 添加弹出的最小值的节点所在链表节点 last-1位置          {              vec.push_back(cur->next);                              push_heap(vec.begin(),vec.end(),compareLess);  // first到last-1是一个有效堆，新加入元素重新生成堆          }      }      return fake.next;    }
        
       
      

注意make_heap进行了重载，加上了最后一个比较参数，也就是重新设定排序规则，本来是从大到小，现在利用compareless函数设定为从小到大。