合并K个升序链表

力扣 23. 合并K个升序链表

题目说明

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

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

提示：
- 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

示例

示例 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:

1 2	输入：lists = [] 输出：[]

示例 3:

1 2	输入：lists = [[]] 输出：[]

笔者理解

此题是一道链表算法问题，在力扣题库中被定义为困难题。

解法

当笔者阅读完此题后，直接采用了遍历链表并记录最小值的方法，让我们来看看具体如何实现的吧。

实现

/**
 * 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) {
        int n = lists.length;
        // 链表数组为空
        if (n == 0) {
            return null;
        }
        // 只有一个链表
        if (n == 1) {
            return lists[0];
        }

        int tick = 0;
        ListNode result = new ListNode(-1);
        ListNode temp = result;

        while (tick != n) {
            tick = 0;
            int min = 10050;
            List<Integer> list = new ArrayList<>();
            
            // 记录最小值以及出现的位置
            for (int i = 0; i < n; i++) {
                if (lists[i] == null) {
                    tick++;
                    continue;
                }
                else {
                    if (lists[i].val < min) {
                        min = lists[i].val;
                        list.clear();
                        list.add(i);
                    }
                    else if (lists[i].val == min) {
                        list.add(i);
                    }
                }
            }

            // 值记录以及链表移动
            for (int i : list) {
                temp.next = lists[i];
                temp = temp.next;
                lists[i] = lists[i].next;
            }

        }

        return result.next;
    }
}