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
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
|
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
|