21.合并两个有序链表

一、题目本质线性归并Merge——归并排序核心操作二、解法1.迭代ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy(0); // 栈上哨兵省去delete ListNode* tail dummy; // tail 始终指向结果链表末尾 while (list1 list2) { if (list1-val list2-val) { tail-next list1; list1 list1-next; } else { tail-next list2; list2 list2-next; } tail tail-next; } tail-next list1 ? list1 : list2; // 拼接剩余 return dummy.next; }2.递归ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } }三、复杂度分析四、变形训练变体1去重合并要求相同值的结点只保留一个两个指针都前进。变体2降序合并1当输入也为降序时直接修改比较符号。2输入为升序输出为降序采用头插法ListNode* mergeTwoListsDesc(ListNode* l1, ListNode* l2) { ListNode* result nullptr; // 无哨兵直接头插 while (l1 l2) { ListNode** smaller (l1-val l2-val) ? l1 : l2; ListNode* node *smaller; *smaller (*smaller)-next; node-next result; // 头插到结果 result node; } // 剩余部分也要头插略或先合并再反转整个链表更简单 return result; }变体3K路归并(1)利用分支归并两两合并。ListNode* mergeKListsDivide(vectorListNode* lists, int l, int r) { if (l r) return lists[l]; if (l r) return nullptr; int mid (l r) / 2; ListNode* left mergeKListsDivide(lists, l, mid); ListNode* right mergeKListsDivide(lists, mid 1, r); return mergeTwoLists(left, right); // 复用两链表合并 }(2)采用最小堆优先队列ListNode* mergeKLists(vectorListNode* lists) { // 小顶堆按结点值排序 auto cmp [](ListNode* a, ListNode* b) { return a-val b-val; }; priority_queueListNode*, vectorListNode*, decltype(cmp) pq(cmp); // 每个链表的头结点入堆 for (auto head : lists) { if (head) pq.push(head); } ListNode dummy(0); ListNode* tail dummy; while (!pq.empty()) { ListNode* node pq.top(); pq.pop(); tail-next node; tail tail-next; if (node-next) pq.push(node-next); // 下一个结点入堆 } return dummy.next; }