How to merge K sorted linked lists in golang
This article introduces how to merge K sorted lists in golang, the content is very detailed, interested friends can refer to, hope to be helpful to you.
Merge k sorted linked lists and return the merged sorted linked list. Please analyze and describe the complexity of the algorithm.
Example:
Enter:
[
1-> 4-> 5
1-> 3-> 4
2-> 6
]
Output: 1-> 1-> 2-> 3-> 4-> 4-> 5-> 6
Ideas for solving the problem:
This is an array + linked list combination problem. Seeing that the linked list is in order, we first think of the linked list merge sub-problem.
1, which is an extension based on merging two ordered linked lists
2, simple ideas
The second start will be merged into the first one in turn, with a complexity of O (krypn)
3, idea 2, pairwise merging, complexity O (logk*n)
4. Note that the length may be odd, even if it is even, it may be odd after pairwise merging, which requires special treatment, otherwise the problem of array crossing the boundary is very difficult to deal with, and it is easy to loop.
5. Expand the idea.
Use the priority queue, merge the smallest elements each time, and then queue the next element of the current linked list until the queue is empty
Code implementation
/ * Definition for singly-linked list. * type ListNode struct {* Val int * Next * ListNode *} * / func mergeKLists (lists [] * ListNode) * ListNode {k:=len (lists) if karma 0 {return nil} for k > 1 {if k% 2 room1 {lists [0] = merge (lists [0], lists [k-1])