LeetCode刷题实战23：合并K个升序链表-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做合并K个升序链表，我们先来看题面：

https://leetcode-cn.com/problems/merge-k-sorted-lists/

Given an array of linked-lists lists, each linked list is sorted in ascending order.

Merge all the linked-lists into one sort linked-list and return it.

题意

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

样例


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

题解

暴力破解法：其中n为lists数组的长度，m为lists数组中链表总节点个数

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n;
        if (null == lists || (n = lists.length) == 0) {
            return null;
        }
        ListNode[] curs = new ListNode[n];
        for (int i = 0; i < n; i++) {
            curs[i] = lists[i];
        }
        ListNode dummyHead = new ListNode(-1), cur = dummyHead;
        do {
            //index索引的作用是寻找一个非空的链表
            int index = 0;
            for (int i = 0; i < n; i++) {
                if (curs[i] != null) {
                    break;
                }
                index++;
            }
            if (index == n) {
                break;
            }
            int minIndex = index;
            for (int i = index + 1; i < n; i++) {
                if (curs[i] != null && curs[i].val < curs[minIndex].val) {
                    minIndex = i;
                }
            }
            cur.next = curs[minIndex];
            cur = cur.next;
            curs[minIndex] = curs[minIndex].next;
        } while (true);
        return dummyHead.next;
    }
}

优先队列：其中m为lists数组中链表总节点个数。

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n;
        if (null == lists || (n = lists.length) == 0) {
            return null;
        }
        PriorityQueue pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            ListNode cur = lists[i];
            while (cur != null) {
                pq.add(cur.val);
                cur = cur.next;
            }
        }
        ListNode dummyHead = new ListNode(-1), cur = dummyHead;
        while (!pq.isEmpty()) {
            cur.next = new ListNode(pq.poll());
            cur = cur.next;
        }
        return dummyHead.next;
    }
}

两两合并链表：其中n为lists数组的长度，m为lists数组中链表总节点个数

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n;
        if (null == lists || (n = lists.length) == 0) {
            return null;
        }
        ListNode result = lists[0];
        for (int i = 1; i < n; i++) {
            result = mergeTwoLists(result, lists[i]);
        }
        return result;
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur1 = l1, cur2 = l2, dummyHead = new ListNode(-1), cur = dummyHead;
        while (cur1 != null || cur2 != null) {
            if (cur1 == null) {
                cur.next = cur2;
                cur2 = cur2.next;
            } else if (cur2 == null) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else if (cur1.val > cur2.val) {
                cur.next = cur2;
                cur2 = cur2.next;
            } else {
                cur.next = cur1;
                cur1 = cur1.next;
            }
            cur = cur.next;
        }
        return dummyHead.next;
    }
}