js 合并K个升序链表
时间: 2023-10-04 21:11:41 浏览: 64
可以使用归并排序的思想来解决这个问题:
1. 将 K 个链表两两合并,得到 K/2 个链表;
2. 将上一步得到的 K/2 个链表再两两合并,得到 K/4 个链表;
3. 重复上述步骤,直到只剩下一个链表。
以下是 JavaScript 代码实现:
```javascript
function mergeKLists(lists) {
if (lists.length === 0) {
return null;
}
while (lists.length > 1) {
let mergedLists = [];
for (let i = 0; i < lists.length; i += 2) {
let l1 = lists[i];
let l2 = (i + 1 < lists.length) ? lists[i + 1] : null;
mergedLists.push(mergeTwoLists(l1, l2));
}
lists = mergedLists;
}
return lists[0];
}
function mergeTwoLists(l1, l2) {
let dummy = new ListNode(0);
let current = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 !== null) ? l1 : l2;
return dummy.next;
}
```
其中 `ListNode` 表示链表节点的类,`val` 表示节点的值,`next` 表示指向下一个节点的指针。