LeetCode 2
Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/merge-two-sorted-lists
Indice
On pourra écrire une fonction récursive.
Si vous avez terminé l'exercice, vous pouvez faire ce prolongement (plus difficile) : https://leetcode.com/problems/merge-k-sorted-lists
Indice
Réutiliser la fonction précédente pour fusionner deux listes.
L'idéal est de résoudre ce problème en O(n log (k)) où n est la somme des tailles des listes et k le nombre de listes.
Solution
Solution en O(nlog(k)) avec une approche diviser pour régner (où n = somme des tailles des listes et k = nombre de listes) :
l1= fusionner récursivement les k/2 premières listesl2= fusionner récursivement les k/2 dernières listes- retourner la fusion (avec mergeTwoLists) de
l1etl2
Chaque fusion s'effectue en O(n) et il y a log(k) fusions, d'où la complexité en O(nlog(k))
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (list1 == NULL) return list2;
if (list2 == NULL) return list1;
if (list1->val <= list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
if (list1->val > list2->val) {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
return NULL;
}
struct ListNode* merge(struct ListNode** lists, int i, int j) {
if(i + 1 == j) return lists[i];
if(i == j) return NULL;
int m = (i + j)/2;
return mergeTwoLists(merge(lists, i, m), merge(lists, m, j));
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
return merge(lists, 0, listsSize);
}