Challenge
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.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
APPROACH
This would be the first time I would be learning linked list
so this took quite some time to figure out. However, let's jump right in.
I love this definition of linked list from freecodecamp: Linked Lists are a data structure that store data in the form of a chain. The structure of a linked list is such that each piece of data has a connection to the next one (and sometimes the previous data as well). Each element in a linked list is called a node
You can learn more about Linked lists here
Aproach
Having understood links, I rewrote my algorithm to solve the challenge this way:
Loop through the k
linked-lists
list.Append the node element of the linked list to a new array.
If there are no empty list and list length equals one, sort new array.
Create a head node from the sorted array:
this is the first element of the linked list of the next elements of the list would be linked toLoop through rest of the sorted array to link the current element to the previous nodes.
Top comments (0)