DEV Community

Cover image for Merge k sorted list
michael-2509
michael-2509

Posted on

Merge k sorted list

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
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: lists = []
Output: []
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: lists = [[]]
Output: []
Enter fullscreen mode Exit fullscreen mode

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 to

  • Loop through rest of the sorted array to link the current element to the previous nodes.

Top comments (0)