Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1. Title Description

Source: LeetCode

You have an array of linked lists, and each list 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] are in ascending order
  • Lists [I]. Length the sum does not exceed 10^4

Second, train of thought analysis

21. Merge two linked lists into one. Merge two linked lists into one

  • We can iterate through the list and then merge the two lists in turn to get the final result.

We can refine the process a little bit. In the above way, we only merge two lists at a time. Can we merge more than one list at a time?

Divide and conquer

We’re talking about lists in arrays, pairing them up and merging them together. K lists are merged into K / 2K / 2K /2 lists, then K / 4K / 4K /4, K / 8K / 8K /8 lists, etc., and the process is repeated until the final ordered list is achieved

Three, code implementation

class Solution { public static class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } 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 dummy = new ListNode(0); ListNode tail = dummy; ListNode l1 = a, l2 = b; while (l1 ! = null && l2 ! = null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } tail.next = (l1 ! = null ? l1 : l2); return dummy.next; }Copy the code

Complexity analysis

The results

  • Time complexity: O(n∗log(k))O(n*log(k))O(n∗log(k))
  • Space complexity: O(logk)O(logk)O(logk), the space used recursively

Another official solution

Use priority queue merge

We need to maintain the first element of each current linked list that has not been merged. K linked lists have at most K elements that meet this condition. Each time, we select the element with the smallest val attribute to be merged into the answer.

We can optimize this process with priority queues when selecting the smallest elements

Code implementation

class Solution { class Status implements Comparable<Status> { int val; ListNode ptr; Status(int val, ListNode ptr) { this.val = val; this.ptr = ptr; } public int compareTo(Status status2) { return this.val - status2.val; } } PriorityQueue<Status> queue = new PriorityQueue<Status>(); public ListNode mergeKLists(ListNode[] lists) { for (ListNode node: lists) { if (node ! = null) { queue.offer(new Status(node.val, node)); } } ListNode head = new ListNode(0); ListNode tail = head; while (! queue.isEmpty()) { Status f = queue.poll(); tail.next = f.ptr; tail = tail.next; if (f.ptr.next ! = null) { queue.offer(new Status(f.ptr.next.val, f.ptr.next)); } } return head.next; }}Copy the code

Complexity analysis

  • Time complexity: The number of elements in the priority queue does not exceedk, then the time cost of insertion and deletion isO(\log k)At most, there arekn, each point is inserted and deleted once, so the total time cost, namely the progressive time complexity, isO (kn * logk).
  • Space complexity: Priority queues are used, and the number of elements in the priority queue does not exceedk, so the asymptotic space complexity isO(k).

conclusion

This topic is still about lists and Pointers, but it’s expanded from two lists to n lists. We’re going to have to deal with more lists, but the implementation of the process is the same, just recursively.

The official method goes one step further, comparing k lists at a time, then taking the smallest and combining them into new lists.

There’s still a lot to learn. Keep going