23. 合并 K 个升序链表

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

题意:

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例:

image.png

合并链表. 最容易想到的就是依次合并

首先合并 1,2 之后合并3 这样依次合并

如何合并?

因为所提供的链表都是有顺序的 所以采用双指针方式

  • 比较两个节点的值
  • 将较小的节点连接到结果链表
  • 移动较小节点所在链表的指针
  • 移动结果链表的指针
  • 遍历完成后, 剩余节点直接拼接

但很遗憾，这样做的话，每一次合并后的新链表就会非常臃肿，并且在与第 K 个链表合并时，之前链表的节点会多次被访问。

我们可以使用分治的思想解决

为了解决臃肿和重复遍历的问题, 把链表的整体合并转为两两合并链表的子问题

image.png

首先判空

if (lists == null || lists.length == 0) {
    return null;
}

设置间隔, 每次只对间隔的头结点做合并操作

int interval = 1;  // 初始间隔为1
while (interval < n) {  // 当间隔小于链表总数时继续循环

这里使用interval来控制合并的步长，比如：

  • 第一轮：interval = 1，两两合并
  • 第二轮：interval = 2，每次合并相隔2个位置的链表
  • 第三轮：interval = 4，每次合并相隔4个位置的链表

合并

for (int i = 0; i < n - interval; i += interval * 2) {
    lists[i] = merge2Lists(lists[i], lists[i + interval]);
}

合并逻辑

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;

整体如下:

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        int n = lists.length;
        int interval = 1;

        while (interval < n) {
            for (int i = 0; i < n - interval; i += interval * 2) {
                lists[i] = merge2Lists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }

        return lists[0];
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        // 创建哑节点作为合并后链表的头部
        ListNode dummy = new ListNode(0);
        ListNode 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;
    }
}