23. Merge k Sorted Lists
Tags:
Hard
Skills:
Linked List
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu trọng k danh sách liên kết đã được sắp xếp thành một Linked list duy nhất được sắp xếp tăng dần
Approach - Divide and conquer
Ghép từng cặp danh sách cho đến khi chỉ còn một danh sách duy nhất
Cách làm
- Ghép từng cặp danh sách, sau mỗi vòng lặp, số danh sách giảm một nửa
- Lặp lại đến khi chỉ còn một danh sách
Time and space complexity
- TC: O(nlogk)
- k là số lần lặp sẽ giảm đi một nửa sau mỗi vòng lặp từ k → k/2 → k/4 → … → 1
- SC: O(1)
Solution
typescripttypescript
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
14 if (lists.length === 0) return null
15
16 while (lists.length > 1) {
17 const merged: Array<ListNode | null> = [];
18 for (let i = 0; i < lists.length; i += 2) {
19 merged.push(mergeTwoList(lists[i], lists[i + 1] || null))
20 }
21 lists = merged;
22 }
23
24 return lists[0]
25};
26
27function mergeTwoList(list1: ListNode | null, list2: ListNode | null): ListNode | null {
28 const dummy = new ListNode(0);
29 let curr = dummy;
30 while (list1 !== null && list2 !== null) {
31 if (list1.val <= list2.val) {
32 curr.next = list1;
33 list1 = list1.next
34 } else {
35 curr.next = list2;
36 list2 = list2.next;
37 }
38 curr = curr.next;
39 }
40
41 curr.next = list1 || list2;
42 return dummy.next;
43}Approach Min Heap
Luôn lấy node nhỏ nhất trong số các node đầu của danh sách hiện tại
Cách làm
- Cho node đầu của mỗi danh sách vào min_heap
- Mỗi lần lấy node nhỏ nhất ra khỏi heap, nối vào kết quả
- Nếu node đó còn next, tiếp tục cho next vào heap
Solution
typescripttypescript
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
14 const min_heap = new MinPriorityQueue<ListNode>((node) => node.val);
15 for (const head of lists) {
16 if (head) {
17 min_heap.enqueue(head);
18 }
19 }
20
21 const dummy = new ListNode(0);
22 let curr = dummy;
23 while (!min_heap.isEmpty()) {
24 const node = min_heap.dequeue();
25 curr.next = node;
26 curr = curr.next;
27
28 if (node.next) {
29 min_heap.enqueue(node.next);
30 }
31 }
32
33 return dummy.next;
34};