首页 > 代码库 > Merge k Sorted Lists

Merge k Sorted Lists

2024-08-02 10:55:18   214人阅读

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

思路：我的第一个想法是将lists中的链表两两合并排序，这样时间复杂度是o（n），n为所有链表中的数据，结果Time Limit Exceeded了。。。暂时没有想到太好的其他方法，希望有大神能给点思路，我先抛个砖，以下是我未AC的代码：

 

 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<ListNode *> &lists) {12         if(lists.size() == 0)   return NULL;13         14         ListNode *pList=lists[0];15         16         vector<ListNode *>::iterator it=lists.begin()+1;17         for(;it!=lists.end();++it)18         {19             pList=MergeLists(pList,*it);20         }21         22         //for(int i=1;i<lists.size();i++)23         //{24             //pList=MergeLists(pList,lists[i]);25         //}26         27         return pList;28     }29     30     ListNode *MergeLists(ListNode *list1, ListNode *list2)31     {32         ListNode *pList=new ListNode(0);33         ListNode *pHead=pList;34         35         while(list1 && list2)36         {37             if(list1->val > list2->val)38             {39                 pList->next=list2;40                 list2=list2->next;41             }42             else43             {44                 pList->next=list1;45                 list1=list1->next;46             }47             pList=pList->next;48         }49         50         if(!list1)51         {52             pList->next=list2;53         }54         if(!list2)55         {56             pList->next=list1;57         }58         59         pList=pHead;60         pList=pList->next;61         pHead->next=NULL;62         delete(pHead);63         64         return pList;65     }66 };
View Code

 

Merge k Sorted Lists


联系
我们