leetcode23：合并K个升序链表

题目链接

leetcode

题目描述

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 链表结点的定义
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) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    K 个升序链表中，每个链表的头结点的地址放入一个小根堆。
    当小根堆不为空时，取出小根堆的第一个结点，
        若该结点的下一个结点不为空，则放入堆；
        否则，不放入堆。

    时间复杂度：O(k*n*logk)
        n 表示每个升序链表的长度，k 表示升序链表的个数。
        优先队列中的元素不超过 k 个，插入和删除的代价为 O(logk)，
        这里最多有 k*n 个点，每个结点都被插入删除各一次。
    空间复杂度：O(k)
        优先队列中的元素不超过 k 个
*/
class Solution_0 {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        ListNode *dummy = new ListNode(-1), *p = dummy;

        // 将所有链表的头结点加入优先队列
        for (ListNode* head : lists) {
            if (head != nullptr) {
                pq.push(head);
            }
        }

        // 依次从优先队列中取出最小的结点，并更新链表
        while (!pq.empty()) {
            ListNode* q = pq.top(); pq.pop();
            p->next = q;
            p = p->next;
            if (q->next != nullptr) {
                pq.push(q->next);
            }
        }

        return dummy->next;
    }

private:
    struct Compare {
        bool operator() (ListNode* a, ListNode* b) {
            return a->val > b->val; // 小根堆，所以返回 >
        }  
    };
};

/*
    思路同上
*/
class Solution_1 {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<Point> pq;
        ListNode *dummy = new ListNode(-1), *p = dummy;

        // 将所有链表的头节点加入优先队列
        for (ListNode* head : lists) {
            if (head != nullptr) {
                pq.push({head->val, head});
            }
        }

        // 依次从优先队列中取出最小的节点，并更新链表
        while (!pq.empty()) {
            Point t = pq.top(); pq.pop();
            p->next = t.node;
            p = p->next;
            if (t.node->next != nullptr) {
                pq.push({t.node->next->val, t.node->next});
            }
        }

        return dummy->next;
    }

private:
    struct Point {
        int val;
        ListNode* node;
        bool operator< (const Point &rhs) const {
            return val > rhs.val;
        }
    };
};

/*
    分治合并，优化空间复杂度

    基本思想是将 K 个链表分成两半，分别合并，然后合并这两个结果。
    重复这个过程，直到只剩下一个链表，即为最终结果。
    
    时间复杂度：O(L*N*logN)
        设链表数组中有 N 个链表，每个链表的平均长度为 L。
        在最坏情况下，需要合并所有的链表，每层递归都会合并 N/2 个链表。
        递归的层数是 N*logN，每层递归合并链表时的平均时间复杂度是 L，
        所以总的时间复杂度是 O(L*N*logN)。
    空间复杂度：O(logk)
        递归调用会使用到栈空间，其空间复杂度是 O(logN)，
        每次递归都会将问题规模减半。
*/
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if (n == 0) return nullptr;
        if (n == 1) return lists[0];

        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n / 2; i ++) {
                lists[i] = mergeTwoLists(lists[i], lists[i + k]);
            }
            n = k;
        }
        return lists[0];
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *p = dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = l1 != nullptr ? l1 : l2;

        return dummy->next;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<vector<int>> lists_nums = {{1, 4, 5}, {1, 3, 4}, {2, 6}};

    // 创建链表数组
    vector<ListNode*> lists;
    for (auto& nums : lists_nums) {
        lists.push_back(createList(nums));
    }

    // 合并操作
    ListNode* result = solution.mergeKLists(lists);
    // 打印结果
    cout << "Result: ";
    printList(result);

    // 释放内存
    for (ListNode* l : lists) {
        deleteList(l);
    }
    deleteList(result);

    return 0;
}

Golang 代码

package main

import (
	"container/heap"
	"fmt"
)

// ListNode 定义链表结点
type ListNode struct {
	Val  int
	Next *ListNode
}

// 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*
    1.初始化一个最小堆，并将每个链表的头结点加入堆中。
    2.每次从堆中取出最小的结点（堆顶元素），将其添加到合并后的链表中。
    3.将刚刚取出结点的下一个结点（如果存在）加入堆中。
    4.重复步骤 2 和 3，直到堆为空。
    5.返回合并后的链表。

    时间复杂度：O(n*logk)
        其中 n 是所有链表中元素的总数，k 是链表的数量。
        共有 n 个结点需要被处理，每个结点最多被加入堆和从堆中弹出一次，每次操作的时间复杂度是 O(logk)。
        因此，总的时间复杂度是 O(n*logk)。
    空间复杂度：O(k)
        优先队列中的元素不超过 k 个。
*/
func mergeKLists_0(lists []*ListNode) *ListNode {
    // 创建一个最小堆
    h := &MinHeap{}
    heap.Init(h)

    // 将每个链表的头结点加入堆中
    for _, list := range lists {
        if list != nil {
            heap.Push(h, list)
        }
    }

    dummy := &ListNode{}
    cur := dummy
    // 当堆不为空时，进行合并操作
    for h.Len() > 0 {
        // 从堆中取出最小的结点
        node := heap.Pop(h).(*ListNode)
        cur.Next = node
        cur = cur.Next
        // 若最小结点的下一个结点不为空，则将其加入堆中
        if node.Next != nil {
            heap.Push(h, node.Next)
        }
    }

    return dummy.Next
}

// 定义优先队列（最小堆）
type MinHeap []*ListNode

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(*ListNode))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n - 1]
    *h = old[0 : n - 1]
    return x
}

/*
    分治合并，优化空间复杂度
    相比传统的逐一合并链表的方法更加高效，特别是在链表数量 k 较大时。
    通过分治法，将时间复杂度降低到 O(n*logk)，这在处理大量链表时是一个显著的改进。

    1.分解：将 K 个链表分成两半，分别对每一半递归地进行合并操作。
    2.解决：当链表的数量减少到 1 时，递归结束，此时每个链表都是排序好的。
    3.合并：将两个排序好的链表合并成一个排序好的链表。

    时间复杂度：O(nlogk)
        其中 n 是所有链表中元素的总数，k 是链表的数量。
        分解过程将 K 个链表分成两半，需要 O(log k) 的时间。
        合并两个链表需要 O(n) 的时间，因为每个元素最多被比较和移动一次。
    空间复杂度：O(logk)
        主要是由递归调用栈的深度决定的。
        每次递归调用都会将链表数量减半，直到只剩下一个链表。
        因此，递归调用的深度是 O(log K)。
*/
func mergeKLists(lists []*ListNode) *ListNode {
    length := len(lists)
    if length == 0 {
        return nil
    }
    // 递归结束条件
    if length == 1 {
        return lists[0];
    }

    // 分治法：链表分为两部分，分别合并
    // 递归实现
    mid := length / 2
    left := mergeKLists(lists[:mid])
    right := mergeKLists(lists[mid:])
    return mergeTwoList(left, right)

    // 非递归实现
    // interval := 1
    // for interval < len(lists) {
    //     for i := 0; i + interval < len(lists); i += 2 * interval {
    //         lists[i] = mergeTwoList(lists[i], lists[i + interval])
    //     }
    //     interval *= 2
    // }
    // return lists[0]
}

func mergeTwoList(l1, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    dummy := &ListNode{}
    p := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            p.Next = l1
            l1 = l1.Next
        } else {
            p.Next = l2
            l2 = l2.Next
        }
        p = p.Next
    }
    if l1 != nil {
        p.Next = l1
    } else {
        p.Next = l2
    }

    return dummy.Next
}

func main() {
    // 测试用例
    testCases := []struct {
        lists    [][]int
        expected []int
    }{
        {
            lists:    [][]int{{1,4,5}, {1,3,4}, {2,6}},
            expected: []int{1,1,2,3,4,4,5,6},
        },
        {
            lists:    [][]int{},
            expected: []int{},
        },
        {
            lists:    [][]int{{}},
            expected: []int{},
        },
    }

    for i, tc := range testCases {
        // 将输入数组转换为链表
        lists := make([]*ListNode, len(tc.lists))
        for j, values := range tc.lists {
            lists[j] = createLinkedList(values)
        }
        // 打印每个链表
		fmt.Printf("Test Case %d, Input: lists = ", i+1)
		for _, head := range lists {
			fmt.Printf("%v ", printLinkedList(head))
		}
        fmt.Println()

        // 合并链表
        result := mergeKLists(lists)
        resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}