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 listes
• l2 = fusionner récursivement les k/2 dernières listes
• retourner la fusion (avec mergeTwoLists) de l1 et l2

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);
}