23. 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入：lists = [] 输出：[]
示例 3：
输入：lists = [[]] 输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 42.2 MB, 提交时间: 2023-08-12 08:57:28
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists)
if (head != null)
pq.offer(head);
ListNode dummy = new ListNode(); // 哨兵节点，作为合并后链表头节点的前一个节点
ListNode cur = dummy;
while (!pq.isEmpty()) { // 循环直到堆为空
ListNode node = pq.poll(); // 剩余节点中的最小节点
if (node.next != null) // 下一个节点不为空
pq.offer(node.next); // 下一个节点有可能是最小节点，入堆
cur.next = node; // 合并到新链表中
cur = cur.next; // 准备合并下一个节点
}
return dummy.next; // 哨兵节点的下一个节点就是新链表的头节点
}
}
python3 解法, 执行用时: 76 ms, 内存消耗: 19.5 MB, 提交时间: 2023-08-12 08:57:03
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
ListNode.__lt__ = lambda a, b: a.val < b.val # 让堆可以比较节点大小
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
cur = dummy = ListNode() # 哨兵节点，作为合并后链表头节点的前一个节点
h = [head for head in lists if head] # 初始把所有链表的头节点入堆
heapify(h) # 堆化
while h: # 循环直到堆为空
node = heappop(h) # 剩余节点中的最小节点
if node.next: # 下一个节点不为空
heappush(h, node.next) # 下一个节点有可能是最小节点，入堆
cur.next = node # 合并到新链表中
cur = cur.next # 准备合并下一个节点
return dummy.next # 哨兵节点的下一个节点就是新链表的头节点
golang 解法, 执行用时: 8 ms, 内存消耗: 5.4 MB, 提交时间: 2023-08-12 08:56:09
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
h := hp{}
for _, head := range lists {
if head != nil {
h = append(h, head)
}
}
heap.Init(&h) // 堆化
dummy := &ListNode{} // 哨兵节点，作为合并后链表头节点的前一个节点
cur := dummy
for len(h) > 0 { // 循环直到堆为空
node := heap.Pop(&h).(*ListNode) // 剩余节点中的最小节点
if node.Next != nil { // 下一个节点不为空
heap.Push(&h, node.Next) // 下一个节点有可能是最小节点，入堆
}
cur.Next = node // 合并到新链表中
cur = cur.Next // 准备合并下一个节点
}
return dummy.Next // 哨兵节点的下一个节点就是新链表的头节点
}
type hp []*ListNode
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val } // 最小堆
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(*ListNode)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
javascript 解法, 执行用时: 116 ms, 内存消耗: 47.8 MB, 提交时间: 2023-08-12 08:55:39
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
let pq = new MinPriorityQueue({priority: e => e.val});
for (const head of lists)
if (head) pq.enqueue(head);
let dummy = new ListNode(); // 哨兵节点，作为合并后链表头节点的前一个节点
let cur = dummy;
while (!pq.isEmpty()) { // 循环直到堆为空
const node = pq.dequeue().element; // 剩余节点中的最小节点
if (node.next) // 下一个节点不为空
pq.enqueue(node.next); // 下一个节点有可能是最小节点，入堆
cur.next = node; // 合并到新链表中
cur = cur.next; // 准备合并下一个节点
}
return dummy.next; // 哨兵节点的下一个节点就是新链表的头节点
};
javascript 解法, 执行用时: 88 ms, 内存消耗: 46 MB, 提交时间: 2023-08-12 08:55:11
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
// 21. 合并两个有序链表
var mergeTwoLists = function (list1, list2) {
let dummy = new ListNode(); // 用哨兵节点简化代码逻辑
let cur = dummy; // cur 指向新链表的末尾
while (list1 && list2) {
if (list1.val < list2.val) {
cur.next = list1; // 把 list1 加到新链表中
list1 = list1.next;
} else { // 注：相等的情况加哪个节点都是可以的
cur.next = list2; // 把 list2 加到新链表中
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 ? list1 : list2; // 拼接剩余链表
return dummy.next;
};
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
// 合并从 lists[i] 到 lists[j-1] 的链表
function dfs(i, j) {
const m = j - i;
if (m === 0) return null; // 注意输入的 lists 可能是空的
if (m === 1) return lists[i]; // 无需合并，直接返回
const left = dfs(i, i + (m >> 1)); // 合并左半部分
const right = dfs(i + (m >> 1), j); // 合并右半部分
return mergeTwoLists(left, right); // 最后把左半和右半合并
}
return dfs(0, lists.length);
};
golang 解法, 执行用时: 4 ms, 内存消耗: 5 MB, 提交时间: 2023-08-12 08:54:20
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1, list2 *ListNode) *ListNode {
dummy := &ListNode{} // 用哨兵节点简化代码逻辑
cur := dummy // cur 指向新链表的末尾
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
cur.Next = list1 // 把 list1 加到新链表中
list1 = list1.Next
} else { // 注：相等的情况加哪个节点都是可以的
cur.Next = list2 // 把 list2 加到新链表中
list2 = list2.Next
}
cur = cur.Next
}
// 拼接剩余链表
if list1 != nil {
cur.Next = list1
} else {
cur.Next = list2
}
return dummy.Next
}
func mergeKLists(lists []*ListNode) *ListNode {
m := len(lists)
if m == 0 { // 注意输入的 lists 可能是空的
return nil
}
if m == 1 { // 无需合并，直接返回
return lists[0]
}
left := mergeKLists(lists[:m/2]) // 合并左半部分
right := mergeKLists(lists[m/2:]) // 合并右半部分
return mergeTwoLists(left, right) // 最后把左半和右半合并
}
cpp 解法, 执行用时: 136 ms, 内存消耗: 12.7 MB, 提交时间: 2023-08-12 08:52:41
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *ans = nullptr;
for (size_t i = 0; i < lists.size(); ++i) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
};
java 解法, 执行用时: 99 ms, 内存消耗: 42.3 MB, 提交时间: 2023-08-12 08:52:09
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode ans = null;
for (int i = 0; i < lists.length; ++i) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 42.4 MB, 提交时间: 2023-08-12 08:48:14
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int lo, int hi) {
if (lo == hi) {
return lists[lo];
}
int mid = lo + (hi - lo) / 2;
ListNode l1 = merge(lists, lo, mid);
ListNode l2 = merge(lists, mid + 1, hi);
return merge2Lists(l1, l2);
}
private ListNode merge2Lists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 == null? l2: l1;
return dummyHead.next;
}
}
python3 解法, 执行用时: 64 ms, 内存消耗: 18.8 MB, 提交时间: 2022-08-30 11:45:22
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:return
import heapq
queue=[]
for l in lists:#将lists的值放进小根堆
head=l
while head:
heapq.heappush(queue,head.val)
head=head.next
dummy=ListNode(0)#构造虚拟节点
cur=dummy
while queue:#将堆顶取出连接成链表
cur.next=ListNode(heapq.heappop(queue))
cur=cur.next
return dummy.next
python3 解法, 执行用时: 80 ms, 内存消耗: 26.8 MB, 提交时间: 2022-08-02 15:30:29
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:return
def merge2Lists(l1,l2):#两有序链表合并
if not l1:return l2
if not l2:return l1
if l1.val<l2.val:
l1.next=merge2Lists(l1.next,l2)
return l1
else:
l2.next=merge2Lists(l1,l2.next)
return l2
def helper(l,r):#二分法 使所有链表两两合并
if l==r:return lists[l]
n=len(lists)
mid=(l+r)>>1
l1=helper(l,mid)
l2=helper(mid+1,r)
return merge2Lists(l1,l2)
return helper(0,len(lists)-1)
python3 解法, 执行用时: 64 ms, 内存消耗: 18.7 MB, 提交时间: 2022-08-02 15:29:59
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
nums=[]
for l in lists: #将所有列表的值取出来放进数组
j=l
while j:
nums.append(j.val)
j=j.next
nums.sort() #对数组排序
dummy=ListNode(0)
head=dummy
for i in range(len(nums)):#将数组的值连接成链表
head.next=ListNode(nums[i])
head=head.next
return dummy.next