This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

First of all, I would like to clarify that every algorithm problem has multiple solutions. We will only talk about several excellent solutions in LeetCode, hoping to help you. Let’s first look at the description of the problem

I. Title Description:

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

Ii. Analysis of Ideas:

Before solving the problem of “merge K sorted lists”, let’s look at a simpler problem: how do you merge two ordered lists? Given that the length of linked list AA and BB are both NN, how can the merge be completed at the time cost of O(n)O(n) and the space cost of O(1)O(1)? This question often arises in interviews. In order to achieve a space cost of O(1)O(1), we aim to “adjust the next pointer to the linked list element in place to complete the merge”. Here are the steps and considerations for merging, which can be skipped for those familiar with the issue. This section recommends reading in conjunction with the code.

First we need a variable head to hold the head of the merged list. You can set head to a dummy head (the val attribute of head does not hold any value). This makes it easier to write the code.

We need a pointer tail to record the previous position of an insertion position, and two Pointers aPtr and bPtr to record the first of the unmerged parts of AA and BB. Notice that tail is not the next insertion position, and that the elements pointed to by aPtr and bPtr are in the “pending merge” state, meaning that they have not been merged into the final list. Of course you can give them other definitions, but the implementation will be different depending on the definition.

When neither aPtr nor bPtr is empty, val is used to know the smaller merge; If the aPtr is empty, merge the entire bPtr and subsequent elements; The same is true if bPtr is null.

When merging, adjust tail’s next attribute first, then move tail and *Ptr (aPtr or bPtr) later. Is there a sequence between tail and *Ptr? They are the same as which moves first and which moves last, and do not change the next pointer of any element

Code demo

public ListNode mergeTwoLists(ListNode a, ListNode b) { if (a == null || b == null) { return a ! = null ? a : b; } ListNode head = new ListNode(0); ListNode tail = head, aPtr = a, bPtr = b; while (aPtr ! = null && bPtr ! = null) { if (aPtr.val < bPtr.val) { tail.next = aPtr; aPtr = aPtr.next; } else { tail.next = bPtr; bPtr = bPtr.next; } tail = tail.next; } tail.next = (aPtr ! = null ? aPtr : bPtr); return head.next; }Copy the code

Complexity analysis

Time complexity: O(n)O(n). Space complexity: O(1)O(1)

Brush question summary

If you have other ideas, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, good ideas and code is more meaningful to learn, let’s work together