合并k个已排序的链表C++
时间: 2024-03-17 07:47:28 浏览: 16
可以使用分治法来合并k个已排序的链表。具体做法如下:
1. 将k个链表分成两个子问题:合并前k/2个链表和合并后k-k/2个链表。
2. 对每个子问题递归地调用合并函数,直到只剩下一个链表。
3. 对两个已排序的链表进行合并,可以使用双指针法,同时遍历两个链表,将较小的节点依次加入新的链表中。
4. 返回合并后的链表。
下面是C++代码实现:
```C++
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;
}
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
if (n == 0) return nullptr;
if (n == 1) return lists[0];
int mid = n / 2;
vector<ListNode*> left(lists.begin(), lists.begin() + mid);
vector<ListNode*> right(lists.begin() + mid, lists.end());
ListNode* l1 = mergeKLists(left);
ListNode* l2 = mergeKLists(right);
return mergeTwoLists(l1, l2);
}
```