[c++]合并排序多个已排好序的单项链表-白红宇

[c++]合并排序多个已排好序的单项链表

阅读量：5908 次

发布时间：2019-06-19

本文共 2242 字，大约阅读时间需要 7 分钟。

题目来源：Leetcode

题目描述：

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

Example:

Input:[  1->4->5,  1->3->4,  2->6]Output: 1->1->2->3->4->4->5->6

思路：不断合并两个链直到所有合并完成 $O (k N)$

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
     
      & lists) {12         ListNode* r=NULL;13         if(lists.size()==0) return r;14         for(int i=0;i
      
       val<=r2->val) { r1->next=mergeTwo(r1->next,r2); return r1;}25         else { r2->next=mergeTwo(r1,r2->next); return r2;}26     }27 };

附加思路：将所有链表不断切半到只剩下两个，将其合并，回到上一层，将其合并

附加思路：先遍历所有链表把他们的值放入一个数组，放的时候就排序好的放，然后把链表连起来成一个链表，把数组的值依次赋值

Time complexity : $O(N\log N)O(NlogN) where NN is the total number of nodes.$

Collecting all the values costs

A stable sorting algorithm costs $O(N\log N)O(NlogN) time.$

Iterating for creating the linked list costs

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
     
      & lists) {12         ListNode* r=NULL;13         if(lists.size()==0) return r;14         vector
      
        m;15         for(int i=0;i
       
        val);t=t->next;}20         }21         QuickSort(m,0,m.size()-1);22         r=lists[0];23         int j=0;24         for(int i=0;i
        
         next!=NULL)28             {29                 t->val=m[j];30                 ++j;31             }32             t->val=m[j];33             if(i+1
         
          next=lists[i+1];34         }35         return r;36     }37     void QuickSort(vector
          
           & list,int p,int r)//快排38 {39 40 if(p

& list,int p,int r)47 {48 int i=p,j=r+1;49 int x=list[p];50 while(1)51 {52 while(list[++i]

x);54 if(i>=j) break;55 int temp=list[i];56 list[i]=list[j];57 list[j]=temp;58 }59 list[p]=list[j];60 list[j]=x;61 return j;62 }63 };