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.
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 :
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.
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.
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.
End of algorithm.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode *left, ListNode *right) {
ListNode *dummy = new ListNode(-1);
ListNode *temp = dummy;
while (left != nullptr && right != nullptr) {
if (left -> val < right -> val) {
temp -> next = left;
temp = temp -> next;
left = left -> next;
}
else {
temp -> next = right;
temp = temp -> next;
right = right -> next;
}
}
while (left != nullptr) {
temp -> next = left;
temp = temp -> next;
left = left -> next;
}
while (right != nullptr) {
temp -> next = right;
temp = temp -> next;
right = right -> next;
}
return dummy -> next;
}
ListNode* mergeSort(vector< ListNode*>& lists, int start, int end) {
if (start == end)
return lists[start];
int mid = start + (end - start) / 2;
ListNode *left = mergeSort(lists, start, mid);
ListNode *right = mergeSort(lists, mid + 1, end);
return merge(left, right);
}
ListNode* mergeKLists(vector< ListNode*>& lists) {
if (lists.size() == 0)
return nullptr;
return mergeSort(lists, 0, lists.size() - 1);
}
};
class Solution {
public ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(-1);
ListNode temp = dummy;
while (left != null && right != null) {
if (left.val < right.val) {
temp.next = left;
temp = temp.next;
left = left.next;
} else {
temp.next = right;
temp = temp.next;
right = right.next;
}
}
while (left != null) {
temp.next = left;
temp = temp.next;
left = left.next;
}
while (right != null) {
temp.next = right;
temp = temp.next;
right = right.next;
}
return dummy.next;
}
public ListNode mergeSort(List lists, int start, int end) {
if (start == end) {
return lists.get(start);
}
int mid = start + (end - start) / 2;
ListNode left = mergeSort(lists, start, mid);
ListNode right = mergeSort(lists, mid + 1, end);
return merge(left, right);
}
public ListNode mergeKLists(List lists) {
if (lists.size() == 0) {
return null;
}
return mergeSort(lists, 0, lists.size() - 1);
}
}
class Solution:
def merge(self, left: ListNode, right: ListNode) -> ListNode:
dummy = ListNode(-1)
temp = dummy
while left and right:
if left.val < right.val:
temp.next = left
temp = temp.next
left = left.next
else:
temp.next = right
temp = temp.next
right = right.next
while left:
temp.next = left
temp = temp.next
left = left.next
while right:
temp.next = right
temp = temp.next
right = right.next
return dummy.next
def mergeSort(self, lists: List[ListNode], start: int, end: int) -> ListNode:
if start == end:
return lists[start]
mid = start + (end - start) // 2
left = self.mergeSort(lists, start, mid)
right = self.mergeSort(lists, mid + 1, end)
return self.merge(left, right)
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
return self.mergeSort(lists, 0, len(lists) - 1)
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
Login/Signup to comment