“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

Merge K sorted linked lists

Merge K ascending linked lists

Topic describes

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

The sample

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

The problem solving

Solution one: sequential merge

Train of thought

Merging k ordered lists, it’s easy to think of merging two ordered lists. Merging two ordered lists is easy, but we definitely want to do it in O(n) time and O(1) space. Here is a general review of the idea of two ordered linked lists

Merges two ordered lists

  • Define a dummy header, dummyHead, that does not store anything, mainly to facilitate merging
  • You then define a prev pointer that points to the position preceding the position to be inserted
  • Finally, define currNode1 and currNode2 to point to the nodes to be inserted in the two linked lists respectively
  • When currNode1 and currNode2 are not empty, insert the value with the smallest value after the prev. When one of currNode1 and currNode2 is empty, insert the rest of the other list after prev

Now that we know how to merge two ordered lists, it’s easy to merge k ordered lists, two ordered lists of two

code

Func MergeTwoList(head1 *ListNode, head2 *ListNode) *ListNode { if head1 == nil { return head2 } else if head2 == nil { return head1 } dummyHead := &ListNode{} prev := dummyHead currNode1, currNode2 := head1, head2 for currNode1 ! = nil && currNode2 ! = nil { if currNode1.Val <= currNode2.Val { prev.Next = currNode1 currNode1 = currNode1.Next } else { prev.Next = currNode2 currNode2 = currNode2.Next } prev = prev.Next } if currNode1 == nil { prev.Next = currNode2 } if currNode2 == Nil {prev.Next = currNode1} return dummyhead. Next} // Sequential merge - mergeK ordered lists func mergeKLists(Lists []*ListNode) *ListNode { baseList := &ListNode{math.MinInt32, nil} for i := 0; i < len(lists); i++ { baseList = MergeTwoList(baseList, lists[i]) } return baseList.Next }Copy the code

Solution two: divide and conquer

Train of thought

So the idea of divide-and-conquer, which is merge sort, is to split the numbers into sufficiently small intervals, and then merge the ordered intervals

In this case, a similar idea can be used to split the linked list to be merged. When the list is small enough, it can be combined in pairs

// Divide and conquer, Func MergeKLists2(Lists []*ListNode) *ListNode {return merge(lists, 0, len(lists)-1) } func merge(lists []*ListNode, l, r int) *ListNode { if l == r { return lists[l] } if l > r { return nil } mid := (l+r) >> 2 return MergeTwoList(merge(Lists, L, mid), merge(Lists, mid+1, R))} func MergeTwoList(head1 *ListNode, head2 *ListNode) *ListNode { if head1 == nil { return head2 } else if head2 == nil { return head1 } dummyHead := &ListNode{} prev := dummyHead currNode1, currNode2 := head1, head2 for currNode1 ! = nil && currNode2 ! = nil { if currNode1.Val < currNode2.Val { prev.Next = currNode1 currNode1 = currNode1.Next } else { prev.Next = currNode2 currNode2 = currNode2.Next } prev = prev.Next } if currNode1 == nil { prev.Next = currNode2 } if currNode2 == nil { prev.Next = currNode1 } return dummyHead.Next }Copy the code