Merge K ascending linked lists

Difficulty: difficult

You are given an array of linked lists, each of which has been sorted in ascending order.

Please merge all lists into one ascending list and return the merged list.

Example 1:

Input: lists = [].enlighened by [1 4], [2, 6]] output:,1,2,3,4,4,5,6 [1] : list array is as follows: [1 - > > 5, 4-1 - > 3 - > 4, 6] 2 - > merge them into an ordered list. 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

Example 2:

Input: Lists = [] Output: []Copy the code

Example 3:

Input: Lists = [[]] Output: []Copy the code

Tip:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 ascendingarrangement
  • lists[i].lengthThe sum of does not exceed10 ^ 4

Solution

Language: java

/** * 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) {List<Integer> List = new ArrayList(); for(ListNode node : lists) { while(node ! = null) { list.add(node.val); node = node.next; } } Collections.sort(list); ListNode dummy = new ListNode(); ListNode cur = dummy; for(int i = 0; i < list.size(); i++) { cur.next = new ListNode(list.get(i)); cur = cur.next; } return dummy.next; }}Copy the code