问题链接

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 = [[]]
输出：[]

解题思路

注意审题：“每个链表都已经按升序排列”

1.暴力解法

A. 首先，我们新建一个链表，用来存放结果；
B. 然后，假设有n条链表，我们可以直接看它们表头的数据，将最小的表头数据放到我们的新链表中；同时，将它从原来的链表中进行删除；如果这个链表空了，直接删除链表即可；
C. 不停地进行步骤2，直到将数据全部取出即可得出答案。

2.链表两两合并

这道题其实很简单，你可以将它看作“合并两个顺序链表”的升级版；我们可以将链表两两合并，16个变8个，8个变4个......直到最后只有一个链表，这就是我们的答案。

代码示例（JAVA）

1.暴力解法

/**
 * 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 == null ||lists.length == 0) {
            return null;
        }

        // 放到list里面，待会直接用stream流找最值
        List<ListNode> nodeList = new ArrayList<>();
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                nodeList.add(lists[i]);
            }
        }

        ListNode preHead = new ListNode(-1);
        ListNode temp = preHead;
        while (nodeList.size() > 0) {
            ListNode minNode = nodeList.stream()
                    .min(Comparator.comparingInt(listNode -> listNode.val))
                    .get();
            temp.next = minNode;
            temp = temp.next;
            
            // 把当前最小的数从它的链表中取出去
            ListNode nextNode = minNode.next;
            nodeList.remove(minNode);
            if (nextNode != null) {
                nodeList.add(nextNode);
            }
        }
        
        return preHead.next;
    }
}

执行结果

2.链表两两合并

/**
 * 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) {
        return merge(lists, 0, lists.length - 1);
    }

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

    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;
    }
}

执行结果