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.

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more