Java 合并K个升序链表

合并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 = [[]]

输出[]

题解思路

判断数组是否为空不为空走下面步骤否则返回null

1. 遍历链表数组记录节点个数

2. 按节点个数创建等量大小数组再一次遍历把节点val值存入数组

3. 内置函数Arrays.sort(新建数组名称)对数组元素排序

4. 创建哑节点dummy,遍历数组把数组元素值作为新建节点的val值。

5. 返回节点。

/**
 * 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){
            return null;
        }
        int count = 0;
        for (int i = 0; i < lists.length; i++) {
            ListNode temp = lists[i];
            while (temp != null){
                count++;
                temp = temp.next;
            }
        }
        System.out.println(count);
        int[] arr = new int[count];
        int ind = 0;
        for (int i = 0; i < lists.length; i++) {
            ListNode temp = lists[i];
            while (temp != null){
                arr[ind++] = temp.val;
                temp = temp.next;
            }
        }
        Arrays.sort(arr);
        ListNode dummy = new ListNode(0);
        ListNode d = dummy;
        for (int i = 0; i < arr.length; i++) {
            d.next = new ListNode(arr[i]);
            d = d.next;
        }
        System.out.println(dummy.next);
        return dummy.next;
    }
}