题目描述
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example1:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
解题思路
- 单来说就是不停的对半划分，比如k个链表先划分为合并两个 k/2 个链表的任务，再不停的往下划分，直到划分成只有一个或两个链表的任务，开始合并。
- 举个例子来说比如合并6个链表，那么按照分治法，首先分别合并0和3，1和4，2和5。这样下一次只需合并3个链表，再合并1和3，最后和2合并就可以了。
- 代码中的k是通过 (n+1)/2 计算的，这里为啥要加1呢，这是为了当n为奇数的时候，k能始终从后半段开始，比如当 n=5 时，那么此时 k=3，则0和3合并，1和4合并，最中间的2空出来。当n是偶数的时候，加1也不会有影响，比如当 n=4 时，此时 k=2，那么0和2合并，1和3合并
- 注意第二个循环，应该i是从0开始，到size / 2,而不应该是k（会报内存错误）
/**
* 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) {
int size = lists.size();
if(size == 0){
return nullptr;
}
int i = 0;
while(size > 1){
int k = (size + 1) / 2 ;
for(int i = 0; i < size / 2; i++){ // 这里循环的条件 应该是 size / 2,而不应该是k
lists[i] = mergeTwoList(lists[i], lists[i + k]);
}
size = k;
}
return lists[0];
}
ListNode* mergeTwoList(ListNode* headA, ListNode* headB){
if(headA == nullptr && headB == nullptr){
return nullptr;
}
if(headA == nullptr && headB != nullptr){
return headB;
}
if(headA != nullptr && headB == nullptr){
return headA;
}
ListNode* preNode = new ListNode(-1);
ListNode* copyhead = preNode;
ListNode* nodeA = headA;
ListNode* nodeB = headB;
if(nodeA -> val < nodeB -> val){
preNode -> next = nodeA;
preNode = nodeA;
nodeA = nodeA -> next;
}else{
preNode -> next = nodeB;
preNode = nodeB;
nodeB = nodeB -> next;
}
while(nodeA && nodeB){
if(nodeA -> val < nodeB -> val){
preNode -> next = nodeA;
preNode = nodeA;
nodeA = nodeA -> next;
}else{
preNode -> next = nodeB;
preNode = nodeB;
nodeB = nodeB -> next;
}
}
if(nodeA){
preNode -> next = nodeA;
}
if(nodeB){
preNode -> next = nodeB;
}
return copyhead -> next;
}
};
/**
* 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) {
if(lists.size() == 0){
return NULL;
}
int size = lists.size();
while(size > 1){
int k = (size + 1) / 2;
for(int i = 0; i < size / 2; i++){
lists[i] = merge2Lists(lists[i], lists[i + k]);
}
size = k;
}
return lists[0];
}
ListNode* merge2Lists(ListNode* head1, ListNode* head2){
if(head1 == NULL && head2 == NULL){
return NULL;
}
if(head1 == NULL){
return head2;
}
if(head2 == NULL){
return head1;
}
ListNode* pNode = NULL;
ListNode* pHead = NULL;
ListNode* pNode1 = head1;
ListNode* pNode2 = head2;
if(pNode1 -> val < pNode2 -> val){
pNode = pNode1;
pNode1 = pNode1 -> next;
}else{
pNode = pNode2;
pNode2 = pNode2 -> next;
}
pHead = pNode;
while(pNode1 && pNode2){
if(pNode1 -> val < pNode2 -> val){
pNode -> next = pNode1;
pNode = pNode1;
pNode1 = pNode1 -> next;
}else{
pNode -> next = pNode2;
pNode = pNode2;
pNode2 = pNode2 -> next;
}
}
if(pNode1){
pNode -> next = pNode1;
}
if(pNode2){
pNode -> next = pNode2;
}
return pHead;
}
};
