Merge k Sorted Lists Leetcode Solution

Merge k Sorted Lists Leetcode Problem :

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.

jump game leetcode

Merge k Sorted Lists Leetcode Solution :

Constraints :

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.

Example 1:

  • Input: lists = []
  • Output: []

Intuition :

The solution uses the merge sort algorithm to merge all the linked lists in the input vector into a single sorted linked list. The merge sort algorithm works by recursively dividing the input into halves, sorting each half separately, and then merging the two sorted halves into a single sorted output.

Approach :

  1. Define a function merge that takes two pointers to linked lists as input and merges them in a sorted manner.

    • a. Create a dummy node with a value of -1 and a temporary node pointing to it.
    • b. Compare the first node of the left and right linked lists, and append the smaller one to the temporary node.
    • c. Continue this process until either of the lists becomes empty.
    • d. Append the remaining nodes of the non-empty list to the temporary node.
    • e. Return the next node of the dummy node.
  2. Define a function mergeSort that takes three arguments – a vector of linked lists, a starting index, and an ending index. It performs merge sort on the linked lists from the starting index to the ending index.

    • a. If the starting index is equal to the ending index, return the linked list at that index.
    • b. Calculate the mid index and call mergeSort recursively on the left and right halves of the vector.
    • c. Merge the two sorted linked lists obtained from the recursive calls using the merge function and return the result.
  3. Define the main function mergeKLists that takes the vector of linked lists as input and returns a single sorted linked list.

    • a. If the input vector is empty, return a null pointer.
    • b. Call the mergeSort function on the entire input vector, from index 0 to index k-1, where k is the size of the input vector.
    • c. Return the merged linked list obtained from the mergeSort function call.
  4. End of algorithm.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription