链表篇（一）——合并两个有序链表

目录

​编辑

一、题目本质

二、解法

1.迭代

2.递归

三、复杂度分析

四、变形训练

变体1：去重合并

变体2：降序合并

变体3：K路归并

一、题目本质

线性归并（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; }

变体3：K路归并

(1)利用分支归并，两两合并。

ListNode* mergeKListsDivide(vector<ListNode*>& 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(vector<ListNode*>& lists) { // 小顶堆：按结点值排序 auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, 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; }