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.
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
Input: lists = []
Output: []
Input: lists = [[]]
Output: []
From: LeetCode
Link: 23. Merge k Sorted Lists
Main Idea:
Detailed Explanation:
mergeTwoLists Function:
This function is a basic utility to merge two individual sorted linked lists (l1 and l2). If one list is empty, it returns the other. Otherwise, it compares the current nodes’ values of the two lists and selects the smaller one, then continues merging with the rest.
mergeKListsHelper Function:
This is the recursive function that embodies the divide-and-conquer logic:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
struct ListNode* mergeKListsHelper(struct ListNode** lists, int start, int end) {
if (start > end) return NULL;
if (start == end) return lists[start];
int mid = start + (end - start) / 2;
struct ListNode* left = mergeKListsHelper(lists, start, mid);
struct ListNode* right = mergeKListsHelper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
if (listsSize == 0) return NULL;
return mergeKListsHelper(lists, 0, listsSize - 1);
}