leetcode/23_merge_k_sorted_lists

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

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 editorial, brute_force

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 editorial, brute_force

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