Problem link - Merge K Sorted Singly Linked Lists
Problem Statement:
You are given K sorted singly linked lists. Your task is to merge these K lists into a single sorted linked list and return the head of the merged linked list. The merged linked list should maintain the sorted order of the input lists.
Approach:
The key idea to solve this problem is to use a min-heap (also called a priority queue) to always keep track of the smallest element among all the lists. The heap allows us to efficiently pick the smallest element and merge the lists in sorted order.
-
Step 1: Initialize a priority queue (min-heap). The heap will store nodes from the lists, and we will always pull the node with the smallest value from the heap.
-
Step 2: Insert the first node of each non-empty linked list into the heap. This ensures that the smallest element from each list is available for comparison.
-
Step 3: Start building the merged list by continuously removing the smallest element (i.e., the node with the smallest value) from the heap. Append this node to the result list.
-
Step 4: After removing a node from the heap, if it has a next node in the same list, push the next node into the heap. This way, we keep pulling nodes in sorted order.
-
Step 5: Repeat the process until all nodes from all lists are merged. Once the heap is empty, the merged list is complete.
Time Complexity:
- O(N log K), where N is the total number of nodes and K is the number of lists.
Space Complexity:
- O(K), as we are storing at most K nodes in the heap at any point.