23. 合并 K 个升序链表

题目描述

输入一个链表数组 lists，其中每个链表都已按升序排好。链表用数组表示，如 [1,4,5]。

把所有链表合并成一个升序链表，返回它的头节点。合并结果为空时返回 null。

示例 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.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
每个 lists[i] 都是升序的。
所有 lists[i].length 之和不超过 10^4。

解题思路：最小堆多路归并

最小堆保存每条未耗尽链的当前头部；弹出最小节点后，将其后继入堆。

为什么正确

堆中每条链最多有一个候选节点，堆顶是所有剩余节点中的最小值。

复杂度分析

总节点数 N：时间 O(N log(k+1)+k)，额外空间 O(k)。

易错点

元组里加入唯一序号，避免相同值时 Python 尝试比较节点对象。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

import heapq
from itertools import count

class Solution:
    def mergeKLists(self, lists):
        heap = []
        serial = count()
        for node in lists:
            if node:
                heapq.heappush(heap, (node.val, next(serial), node))
        dummy = ListNode(0)
        tail = dummy
        while heap:
            _, _, node = heapq.heappop(heap)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, next(serial), node.next))
        return dummy.next

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            tail.next = node;
            tail = node;
            if (node.next != null) {
                heap.offer(node.next);
            }
        }
        return dummy.next;
    }
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
        for (ListNode* node : lists) {
            if (node) {
                heap.push(node);
            }
        }
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
        while (!heap.empty()) {
            ListNode* node = heap.top(); heap.pop();
            tail->next = node;
            tail = node;
            if (node->next) {
                heap.push(node->next);
            }
        }
        return dummy->next;
    }
};

type nodeHeap []*ListNode

func (h nodeHeap) Len() int           { return len(h) }
func (h nodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h nodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(x any)        { *h = append(*h, x.(*ListNode)) }
func (h *nodeHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func mergeKLists(lists []*ListNode) *ListNode {
	h := &nodeHeap{}
	for _, node := range lists {
		if node != nil {
			heap.Push(h, node)
		}
	}
	dummy := &ListNode{}
	tail := dummy
	for h.Len() > 0 {
		node := heap.Pop(h).(*ListNode)
		tail.Next = node
		tail = node
		if node.Next != nil {
			heap.Push(h, node.Next)
		}
	}
	return dummy.Next
}

class MinHeap {
    constructor(less) { this.a = []; this.less = less; }
    get size() { return this.a.length; }
    push(x) {
        const a = this.a; a.push(x);
        for (let i = a.length - 1; i > 0;) {
            const p = (i - 1) >> 1;
            if (!this.less(a[i], a[p])) break;
            [a[i], a[p]] = [a[p], a[i]]; i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            for (let i = 0; ;) {
                let m = i; const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.less(a[l], a[m])) m = l;
                if (r < a.length && this.less(a[r], a[m])) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]]; i = m;
            }
        }
        return top;
    }
}

var mergeKLists = function(lists) {
    const heap = new MinHeap((a, b) => a.val < b.val);
    for (const node of lists) {
        if (node) {
            heap.push(node);
        }
    }
    const dummy = new ListNode(0);
    let tail = dummy;
    while (heap.size) {
        const node = heap.pop();
        tail.next = node;
        tail = node;
        if (node.next) {
            heap.push(node.next);
        }
    }
    return dummy.next;
};

class MinHeap<T> {
    private a: T[] = [];
    constructor(private less: (x: T, y: T) => boolean) {}
    get size(): number { return this.a.length; }
    push(x: T): void {
        const a = this.a; a.push(x);
        for (let i = a.length - 1; i > 0;) {
            const p = (i - 1) >> 1;
            if (!this.less(a[i], a[p])) break;
            [a[i], a[p]] = [a[p], a[i]]; i = p;
        }
    }
    pop(): T {
        const a = this.a, top = a[0], last = a.pop()!;
        if (a.length) {
            a[0] = last;
            for (let i = 0; ;) {
                let m = i; const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.less(a[l], a[m])) m = l;
                if (r < a.length && this.less(a[r], a[m])) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]]; i = m;
            }
        }
        return top;
    }
}

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    const heap = new MinHeap<ListNode>((a, b) => a.val < b.val);
    for (const node of lists) {
        if (node) {
            heap.push(node);
        }
    }
    const dummy = new ListNode(0);
    let tail = dummy;
    while (heap.size) {
        const node = heap.pop();
        tail.next = node;
        tail = node;
        if (node.next) {
            heap.push(node.next);
        }
    }
    return dummy.next;
}

载入编辑器，自己跑一遍 →

其他解法

顺序合并最简单但为 O(k·N)；分治和最小堆都是 O(N log k)，分治借用归并排序的结构，堆则每次直接取出全局最小节点。

解法 2：顺序两两合并时间 O(k·N)，空间 O(1)

用 ans 保存已合并的结果，初始为空。依次把每条链表与 ans 做一次「合并两个有序链表」，结果再赋回 ans。N 是节点总数，k 是链表条数。

只需要会合并两条链表，代码最简单。靠前的节点会被反复扫描，k 大时明显慢于堆和分治。

class Solution:
    def mergeKLists(self, lists):
        def merge_two(a, b):
            dummy = ListNode(0)
            tail = dummy
            while a and b:
                if a.val <= b.val:
                    tail.next = a; a = a.next
                else:
                    tail.next = b; b = b.next
                tail = tail.next
            tail.next = a if a else b
            return dummy.next

        ans = None
        for node in lists:
            ans = merge_two(ans, node)
        return ans

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (ListNode node : lists) ans = mergeTwo(ans, node);
        return ans;
    }

    ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }
}

class Solution {
public:
    ListNode* mergeTwo(ListNode* a, ListNode* b) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (a && b) {
            if (a->val <= b->val) { tail->next = a; a = a->next; }
            else { tail->next = b; b = b->next; }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans = nullptr;
        for (ListNode* node : lists) ans = mergeTwo(ans, node);
        return ans;
    }
};

func mergeTwo(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next = a
			a = a.Next
		} else {
			tail.Next = b
			b = b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
	var ans *ListNode
	for _, node := range lists {
		ans = mergeTwo(ans, node)
	}
	return ans
}

var mergeKLists = function(lists) {
    const mergeTwo = (a, b) => {
        const dummy = new ListNode(0);
        let tail = dummy;
        while (a && b) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a ? a : b;
        return dummy.next;
    };
    let ans = null;
    for (const node of lists) ans = mergeTwo(ans, node);
    return ans;
};

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    const mergeTwo = (a: ListNode | null, b: ListNode | null): ListNode | null => {
        const dummy = new ListNode(0);
        let tail = dummy;
        while (a && b) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a ? a : b;
        return dummy.next;
    };
    let ans: ListNode | null = null;
    for (const node of lists) ans = mergeTwo(ans, node);
    return ans;
}

解法 3：分治两两合并时间 O(N log k)，空间 O(log k)

merge(l, r) 返回 lists[l..r] 合并后的链表。区间只剩一条时直接返回，否则从中点拆成两半分别递归，再把两个结果用「合并两个有序链表」合在一起。每个节点在递归树的每一层只被扫描一次，共 log k 层。

与堆的时间复杂度相同，不需要堆结构，额外空间只有递归栈。思路与归并排序完全一致，便于迁移。

class Solution:
    def mergeKLists(self, lists):
        def merge_two(a, b):
            dummy = ListNode(0)
            tail = dummy
            while a and b:
                if a.val <= b.val:
                    tail.next = a; a = a.next
                else:
                    tail.next = b; b = b.next
                tail = tail.next
            tail.next = a if a else b
            return dummy.next

        def merge(l, r):
            if l > r:
                return None
            if l == r:
                return lists[l]
            mid = (l + r) // 2
            return merge_two(merge(l, mid), merge(mid + 1, r))

        return merge(0, len(lists) - 1)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    ListNode merge(ListNode[] lists, int l, int r) {
        if (l > r) return null;
        if (l == r) return lists[l];
        int mid = (l + r) / 2;
        return mergeTwo(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }
}

class Solution {
public:
    ListNode* mergeTwo(ListNode* a, ListNode* b) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (a && b) {
            if (a->val <= b->val) { tail->next = a; a = a->next; }
            else { tail->next = b; b = b->next; }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy.next;
    }

    ListNode* merge(vector<ListNode*>& lists, int l, int r) {
        if (l > r) return nullptr;
        if (l == r) return lists[l];
        int mid = (l + r) / 2;
        return mergeTwo(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, (int)lists.size() - 1);
    }
};

func mergeTwo(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next = a
			a = a.Next
		} else {
			tail.Next = b
			b = b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

func mergeRange(lists []*ListNode, l, r int) *ListNode {
	if l > r {
		return nil
	}
	if l == r {
		return lists[l]
	}
	mid := (l + r) / 2
	return mergeTwo(mergeRange(lists, l, mid), mergeRange(lists, mid+1, r))
}

func mergeKLists(lists []*ListNode) *ListNode {
	return mergeRange(lists, 0, len(lists)-1)
}

var mergeKLists = function(lists) {
    const mergeTwo = (a, b) => {
        const dummy = new ListNode(0);
        let tail = dummy;
        while (a && b) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a ? a : b;
        return dummy.next;
    };
    const merge = (l, r) => {
        if (l > r) return null;
        if (l === r) return lists[l];
        const mid = (l + r) >> 1;
        return mergeTwo(merge(l, mid), merge(mid + 1, r));
    };
    return merge(0, lists.length - 1);
};

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    const mergeTwo = (a: ListNode | null, b: ListNode | null): ListNode | null => {
        const dummy = new ListNode(0);
        let tail = dummy;
        while (a && b) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a ? a : b;
        return dummy.next;
    };
    const merge = (l: number, r: number): ListNode | null => {
        if (l > r) return null;
        if (l === r) return lists[l];
        const mid = (l + r) >> 1;
        return mergeTwo(merge(l, mid), merge(mid + 1, r));
    };
    return merge(0, lists.length - 1);
}

链表专题的其他题目

查看链表全部题目 →