Ćwiczenie #4

Lekcja 13 z 14 w kursie Lista wiązana — struktury danych, część 5 w Coddy.

Wyzwanie

Łatwy

Mając dwie posortowane tablice liczb całkowitych a i b (wartości z dwóch posortowanych list połączonych), napisz funkcję mergeSorted, która zwraca jedną posortowaną tablicę zawierającą wszystkie wartości z obu tablic wejściowych.

Rozwiąż ten problem, używając listy połączonej! Przechodź równolegle przez obie listy, za każdym razem dodając do wyniku mniejszy element z początku listy.

Musisz użyć klasy LinkedList (udostępnionej w pliku linkedlist.<ext> wraz z node.<ext>) — nie używaj wbudowanych funkcji języka, takich jak wbudowane odwracanie tablic, wycinanie fragmentów ani operacje na listach ze standardowej biblioteki, aby obliczyć wynik.

Spróbuj swoich sił

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