合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
时间: 2024-05-14 20:14:26 浏览: 15
这道题可以使用分治的思想来解决。将 k 个链表两两合并,最终得到一个链表。然后再将这个链表和另一个链表合并,一直合并到只剩下一个链表为止。
具体实现可以使用递归来完成。递归的基本条件是只有一个链表或者没有链表,此时直接返回这个链表或者空值。否则,将 k 个链表分成两部分,分别递归地合并这两部分,最终将两个链表合并成一个链表返回。
代码如下:
```
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
int n = lists.size();
return merge(lists, 0, n-1);
}
ListNode* merge(vector<ListNode*>& lists, int left, int right) {
if (left == right) return lists[left];
int mid = (left + right) / 2;
ListNode* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid+1, right);
return mergeTwoLists(l1, l2);
}
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;
}
}
};
```