题目：Merge Two Sorted Lists
合并两个单链表。
思路：
同时遍历两个单链表，比较每个值，较小的取下来放到新的链表的尾部。
注意：判断空链的情况
ListNode* LeetCode::mergeTwoLists(ListNode* l1, ListNode* l2){ if (!l1)return l2; if (!l2)return l1; ListNode* head = nullptr; ListNode* tail = nullptr; if (l1->val < l2->val){//l1为头结点 head = l1; l1 = l1->next; } else{//l2为头结点 head = l2; l2 = l2->next; } tail = head; while (l1 && l2){ if (l1->val < l2->val){//l1较小 tail->next = l1; l1 = l1->next; } else{//l2较小 tail->next = l2; l2 = l2->next; } tail = tail->next; } if (l1)tail->next = l1;//l1链表不空 if (l2)tail->next = l2;//l2链表不空 return head; }
题目：Merge k Sorted Lists
合并k个单链表。
思路：
设置k个链表指针分别通过这些指针来遍历着k个链表；但是不能像上面那样有一个链表为空就跳出，而要当仅有一个链表不空的时候跳出。
所以每当有一个链表遍历到链尾时，就将它的指针删除。
ListNode* LeetCode::mergeKLists(vector<ListNode*>& lists){ vector<ListNode*>p; for (size_t i = 0; i < lists.size(); i++){ if (lists.at(i)){//可能数组中有空链 p.push_back(lists.at(i)); } } ListNode* head = nullptr; ListNode* tail = nullptr; while (p.size() > 1){ int min = 0; for (size_t i = 1; i < p.size(); i++){//找到最小的节点 if (p.at(min)->val > p.at(i)->val)min = i; } if (head){ tail->next = p.at(min);//将最小的节点加入尾部 tail = tail->next; p.at(min) = p.at(min)->next;//最小的链表指向下一个 } else{//第一个节点 head = p.at(min); tail = head; p.at(min) = p.at(min)->next; } for (size_t i = 0; i < p.size(); ){//删除已经指向链尾的指针 if (!p.at(i)){ p.at(i) = p.at(p.size() - 1); p.pop_back(); } else{ ++i; } } } if (p.size()){ if (head)tail->next = p.at(0); else head = p.at(0);//lists中只有一条链表 } return head; }
[LeetCode]Merge Two Sorted Lists
原文：http://www.cnblogs.com/yeqluofwupheng/p/6786570.html