Задачи за допълнително упражнение 22.11.2022

Задача първа - Merge linked lists

Да се напише функция, която получава два сортирани списъка с елементи цели числа, обединява ги в един сортиран списък и връща резултата.

Пример:

Вход: * l1 = [1, 2, 4, 8, 16] * l2 = [1, 2, 3, 5, 7, 9, 11]

Изход:

• [1, 1, 2, 2, 3, 4, 5, 7, 8, 9, 11, 16]

Задача втора

Даден е едносвъран списък, чийто елементи са числа. Напишете функция rearange, която пренарежда елементите, така че първо да бъдат четните числа, после нечетните. Относителната наредба между числата трябва да се запази. Решението ви трябва да работи за O(n) време и O(1) памет.

Пример:

Вход:

• 3 -> 5 -> 2 -> 9 -> 4

Изход:

• 2 -> 4 -> 3 -> 5 -> 9

Задача трета

Даден е свързан списък, чиито елементи са числа. Напишете функция oddEvenList, която пренарежда списъка така, че в първо да бъдат възлите на нечетни позиции а след това тези на четни. Решението ви трябва да работи в O(n) време и O(1) памет. Считаме първата позиция за нечетна.

Пример:

Вход: * 1 -> 2 -> 3 -> 4 -> 5

Изход: * 1 -> 3 -> 5 -> 2 -> 4

Вход: * 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7

Изход: * 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4

Задача четвърта - Reverse nodes in K-group

Да се напише функция, която приема едносвързан списък и естествено число k. За k знаем, че е по - голямо от 0, но по - малко от дължината на списъка. K група наричаме възлите на индекси [0..k-1], [k..2k-1] и тн. Да се обърнат всички K групи.

Пример:

Вход: [1, 2, 3, 4, 5], k = 2

Тук K групите са (1, 2), (3, 4). В резултата те са обърнати.

Изход: [2, 1, 4, 3, 5]

Вход: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17], k = 4

Тук K групите са (1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16). В резултата те са обърнати.

Изход: [4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13, 17]

Задача пета

Нека е даден списък L с елементи стекове. Възлите на L са от тип Node. Да се дефинира подходящо параметризирана функция equalize(L), която размества елементите на стековете така, че да няма два стека в L с разлика в броя на елементите, по-голяма от 1.

Задача шеста

Даден е свързан списък с една връзка L, чийто елементи са опашки. Да се напише функция, което конкатенира всички последователни опашки, чиито елементи отговарят на даден предикат p.