Practice #4
Урок 13 из 14 курса Связный список — Серия «Структуры данных» №5 на Coddy.
Задание
ЛегкоДаны два отсортированных массива целых чисел a и b (значения двух отсортированных связных списков). Напишите функцию mergeSorted, которая возвращает один отсортированный массив, содержащий все значения из обоих входных массивов.
Используйте связный список для решения этой задачи! Пройдите по обоим спискам параллельно, последовательно добавляя меньший головной элемент в результат.
Вы должны использовать класс LinkedList (предоставленный в linkedlist.<ext> вместе с node.<ext>) — не используйте встроенные возможности языка, такие как встроенный разворот массива, срезы или операции со списками из стандартной библиотеки для вычисления результата.
Попробуйте сами
#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;
}
