23_merge_k_sorted_lists

dz / leetcode / 23_merge_k_sorted_lists

Summary

23. Merge K sorted listes You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Node Tree

• URL
• editorial
  • k_way_merge
  • collect_and_sort_brute_force
  • compare_one_by_one
    • compare_one_by_one_priority_queue
• intuition
  • top_item_next
  • brute_force
    • collect_and_sort_brute_force
    • compare_one_by_one
      • compare_one_by_one_priority_queue

Nodes

URL
content	URL
hyperlink	https://leetcode.com/problems/merge-k-sorted-lists/

intuition
content	My intuition says to think of the linked list as an implementation detail, and to focus on the algorithm first.
children	top_item_next, brute_force

top_item_next
content	Since they are all pre-sorted, we can know that at any given point in time, the next item in the list is the first item of any of the k lists (the head)
parents	intuition

brute_force
content	A potential brute force algorithm would involve in each iteration finding the smallest head from each of the k lists, popping it off, and inserting it into a new list. this has a performance of O(max(list[i])*k).
children	collect_and_sort_brute_force (simpler concept), compare_one_by_one (Similar to what I was thinking about.)
parents	intuition

editorial
content	editorial
children	k_way_merge (follow-up reading, this is more information than the editorial), collect_and_sort_brute_force, compare_one_by_one

collect_and_sort_brute_force
content	The brute force approach suggested here involves simply appending all the items into some kind of list object, and then using some sorting algorithm (built into the language) to sort it. Nothing really to it.
parents	brute_force, editorial

compare_one_by_one
content	Compare every k nodes (head of every linked list), and get the node with the smallest value. Append to list.
children	compare_one_by_one_priority_queue (Optimizes approach with prioirty queue)
parents	brute_force, editorial

compare_one_by_one_priority_queue
content	This seems to use a priority queue to do the sorting.
parents	compare_one_by_one
remarks	Solution not explained here, only python code

k_way_merge
content	k-way merge: a specific type of sequence merge algorithms that specialize in taking in k sorted lists and merging them into a single sorted list.
parents	editorial
remarks	This gives way more information about the underlying algorithm than LC
hyperlink	https://en.wikipedia.org/wiki/K-way_merge_algorithm