Esercizio #4

Lezione 13 di 14 del corso Lista concatenata - Serie sulle strutture dati #5 di Coddy.

Sfida

Facile

Date due array di interi ordinate a e b (i valori di due liste concatenate ordinate), scrivi una funzione mergeSorted che restituisca un singolo array ordinato contenente tutti i valori di entrambi gli input.

Usa una lista concatenata per risolvere questo problema! Scorri entrambe le liste in parallelo, inserendo ripetutamente nella lista risultante il valore più piccolo tra quelli in testa.

Devi usare la classe LinkedList (fornita in linkedlist.<ext> insieme a node.<ext>) — non usare funzionalità integrate del linguaggio, come l’inversione integrata degli array, lo slicing o le operazioni sulle liste della libreria standard, per calcolare il risultato.

Provalo tu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"

int main() {
    char line1[8192];
    char line2[8192];
    if (!fgets(line1, sizeof(line1), stdin)) line1[0] = '\0';
    if (!fgets(line2, sizeof(line2), stdin)) line2[0] = '\0';
    int a[4096];
    int alen = 0;
    char* tok = strtok(line1, " \t\r\n");
    while (tok) { a[alen++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
    int b[4096];
    int blen = 0;
    tok = strtok(line2, " \t\r\n");
    while (tok) { b[blen++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
    int rs = 0;
    int* r = mergeSorted(a, alen, b, blen, &rs);
    for (int idx = 0; idx < rs; idx++) {
        if (idx > 0) printf(" ");
        printf("%d", r[idx]);
    }
    printf("\n");
    return 0;
}