23. Merge k Sorted Lists

矫情吗；* 2024-04-18 02:31 58阅读 0赞

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

题意：  
给定若干个以及排好序的链表，让把这些链表合并成一个有序的大的链表。  
链表里面的每个节点，都需要来自原来的的链表，即 最终的结果链表不应该出现新动态申请的节点，如果有新申请的则会报错的。

解题思路：  
通常有两种方法。

*  我们会做两个有序链表的合并，那么K个有序链表一样可以做：K个链表 两两合并得到 K / 2 K/2 K/2个链表，再把这 K / 2 K/2 K/2 个链表再两两合并，直到只剩下一个链表，这个链表就是最终的结果。  
    这里的复杂度是： 合并两个列表需要 O ( n ) O(n) O(n) ,于是第一轮合并时 有 K / 2 K/2 K/2 次合并，第二轮有 k / 4 k/4 k/4次合并。。。于是复杂度为: K 2 O ( n ) + k 4 O ( n ) + ⋅ ⋅ ⋅ \\frac\{K\}\{2\}O(n)+\\frac\{k\}\{4\}O(n)+··· 2KO(n)\+4kO(n)\+⋅⋅⋅ ，这个的上界是  k O ( n ) kO(n) kO(n).  
    代码：

class Solution{ 
    public:
    	ListNode *merge2Lists(ListNode *l1, ListNode *l2)
    	{ 
    		ListNode * rst=NULL,*head=NULL;
    
    		while (l1!=NULL && l2!=NULL)
    		{ 
    			if (l1->val < l2->val)
    			{ 
    				ListNode *tmp = l1;
    				l1 = l1->next;
    				if (rst == NULL)
    				{ 
    					rst = tmp;
    					head = rst;
    					//rst->next = l1;
    				}
    				else
    				{ 
    					
    					rst->next = tmp;
    					rst = rst->next;
    				}
    				
    			}
    			else
    			{ 
    				ListNode * tmp = l2;
    				l2= l2->next;
    				if (rst == NULL)
    				{ 
    					rst = tmp;
    					head = rst;
    				}
    				else
    				{ 
    					rst->next = tmp;
    					rst = rst->next;
    				}
    			}
    			
    		}
    		while (l1!=NULL)
    		{ 
    			ListNode *tmp = l1;
    			l1 = l1->next;
    			if (rst == NULL)
    			{ 
    				rst = tmp;
    			}
    			else
    			{ 
    				rst->next = tmp;
    				rst = rst->next;
    			}
    			
    		}
    		while (l2!=NULL)
    		{ 
    			ListNode *tmp = l2;
    			l2 = l2->next;
    			if (rst == NULL)
    			{ 
    				rst = tmp;
    			}
    			else
    			{ 
    				rst->next = tmp;
    				rst = rst->next;
    			}
    
    			
    		}
    		if (rst)
    		{ 
    			rst->next = NULL;
    		}
    		return head;
    	}
    	ListNode* mergeKLists(vector<ListNode*>& lists) { 
    		deque<ListNode*> head;
    		vector<int> numbers;
    		for (int i = 0; i < lists.size(); i++)
    		{ 
    			ListNode * tmp = lists[i];
                if(tmp)
    			head.push_front(tmp);
    		}
    		while (head.size()>1)
    		{ 
    			//提取出头两个列表进行合并
    			ListNode *l1 = head.back();
    			head.pop_back();
    			ListNode *l2 = head.back();
    			head.pop_back();
    			ListNode *l = merge2Lists(l1, l2);
    			head.push_front(l);
    		}
    		if (head.size() == 1)
    		{ 
    			return head.back();
    		}
    		else
    		{ 
    			return NULL;
    		}
    	}
    };

结果：  
Runtime: 24 ms, faster than 90.67% of C++ online submissions for Merge k Sorted Lists.  
Memory Usage: 11.3 MB, less than 57.14% of C++ online submissions for Merge k Sorted Lists.

*  第二种方法，简单粗暴。首先先遍历所有的链表，把里面的元素和各个节点的指针保存到数组中。接着对元素进行重新排序，需要 O ( n l o g n ) O(nlogn) O(nlogn) 时间。最后再把这些排好序的元素一个个的丢给保存节点的指针数组，把里面的数据域和指针改好，使他们成为一个大链表。综合下来的复杂度为 O ( n ) + O ( n l o g n ) + O ( n ) = O ( n l o g n ) O(n)+O(nlogn)+O(n)=O(nlogn) O(n)\+O(nlogn)\+O(n)=O(nlogn).  
    代码：

class Solution { 
    public:
    	ListNode* mergeKLists(vector<ListNode*>& lists) { 
    		vector<ListNode*> head;
    		vector<int> numbers;
    		for (int i = 0; i < lists.size(); i++)
    		{ 
    			ListNode * tmp = lists[i];
    			while (tmp)
    			{ 
    				numbers.push_back(tmp->val);
    				head.push_back(tmp);
    				tmp = tmp->next;
    			}
    		}
    		sort(numbers.begin(), numbers.end());
    		for (int i = 0; i < numbers.size(); i++)
    		{ 
    			head[i]->val = numbers[i];
    			if ((i + 1) < numbers.size())
    			{ 
    
    				head[i]->next = head[i + 1];
    			}
    			else
    			{ 
    				head[i]->next = NULL;
    			}
    		}
    		if (numbers.size())
    		{ 
    			return head[0];
    		}
    		else
    		{ 
    			return NULL;
    		}
    	}
    };

结果：  
Runtime: 24 ms, faster than 90.67% of C++ online submissions for Merge k Sorted Lists.  
Memory Usage: 11.5 MB, less than 28.57% of C++ online submissions for Merge k Sorted Lists.

两种方法其实差不多，时间和空间的运行结果类似。 猜测测试数据的K和N都比较大或 都比较小。