链表--Merge Two? Sorted List

融合两个有序链表

题目：Merge two sorted linked lists and return it as a new list.

本文介绍两种方法.

方法1：用递归

ListNode *mergeTwoLists(ListNode *L1, ListNode *L2){    if(L1 == NULL)    return L2;if(L2 == NULL)    return L1;if(L1->val < L2->val){//L1的第一个元素比L2的第一个元素小，那么融合L1的第二个元素和L2的所有元素ListNode *right = mergeTwoLists(L1->next,L2);L1->next = right;return L1;}else{ListNode *right = mergeTwoLists(L1,L2->next);L2->next = right;return L2;}return NULL;
}

方法2：非递归

ListNode *mergeTwoSortedLists(ListNode *L1,ListNode *L2)
{if(L1 == NULL)    return  L2;if(L2 == NULL)    return  L1;//头结点由于不确定是哪个,所有用dummyListNode *dummy = new ListNode(0);ListNode *curr = dummy;while(L1 && L2){if(L1->val < L2->val){curr->next = L1;curr = L1;L1 = L1->next;}else{curr->next = L2;curr = L2;L2 = L2->next;}}if(L1) curr->next = L1;if(L2) curr->next = L2;return dummy->next;
}

拓展：Merge K Sorted Lists

方法1：暴力循环融合

//暴力循环解法
ListNode *mergeKSortedLists(vector<ListNode*> &lists)
{if(lists.size() == 0)    return NULL;int len = lists.size();ListNode *p = lists.at(0);for(int i=1;i<len;i++){//复用上面的接口p = mergeTwoSortedLists(p,lists.at(i));}return p;
}

方法2：归并

ListNode *helper(vector<ListNode *> &lists,int left, int right)
{//递归终止条件，当只有一个时链表时直接返回即可if(left > right)    return NULL;if(left == right) return lists[left];int mid =  left + (right - left) / 2;ListNode *leftNode = helper(lists,left,mid);ListNode *rightNode = helper(lists,mid+1,right);return mergeTwoSortedLists(leftNode,rightNode);
}ListNode *mergeKSortedLists(vector<ListNode*> &lists)
{if(lists.size() == 0)    return NULL;return helper(lists,0,lists.size()-1);
}

方法3：最小堆

//这个比较函数会使优先队列的节点值按从小到大排列,小的在开始.
struct greaterNodeList{bool operator()(ListNode *x,ListNode *y){return x->val > y->val;}
}ListNode *mergeKSortedLists(vector<ListNode *> &lists)
{if(lists.size() == 0)    return NULL;if(lists.size() == 1)    return lists[0];priority_queue<ListNode*,vector<ListNode *>,greaterNodeList> q;//将每个队列的头节点放入队列for(int i=0;i<lists.size();i++){if(lists[i])q.push(lists[i]->val);}ListNode *dummy = new ListNode(0);ListNode *currNode = dummy;while(!q.empty()){//取出最小值ListNode *tmpNode = q.top();//弹出最小值q.pop();//如果最小值的下一个不为空，则将下一个插入队列if(tmpNode->next)q.push(tmpNode->next);//将取出来的最小值连接进融合后的链表currNode->next = tmpNode;currNode = currNode->next;currNode->next = NULL;    }return dummy->next;
}