Задачи по темам

Односвязный список

1. Дан односвязный список, нужно развернуть его за O(n) времени и O(1) дополнительной памяти.
2. Дан односвязный список, нужно проверить, есть ли в нём цикл (последний элемент ссылается на какой-то элемент списка, а не на Null)
3. Дан односвязный список с циклом. Определить длину цикла.
4. Дан односвязный список с циклом. Определить длину хвоста (те элементы, которые не участвуют в цикле).
5. Реализовать класс односвязного списка с методом "вернуть k-й с конца элемент".

Подсказка: задачи 2-4 см. тут

Строки

1. Реализуйте алгоритм, определяющий, все ли символы в строке встречаются один раз. При выполнении этого задания нельзя использовать дополнительные структуры данных.
2. Для двух строк напишите метод, определяющий, является ли одна строка перестановкой другой.
3. Реализуйте метод, осуществляющий сжатие строки, на основе счетчика повторяющихся символов. Например, строка aabcccccaaa должна превратиться в a2b1c5a3. Если «сжатая» строка оказывается длиннее исходной, метод должен вернуть исходную строку.
4. Допустим, что существует метод isSubstring, проверяющий, является ли одно слово подстрокой другого. Для двух строк, s1 и s2, напишите код проверки, получена ли строка s2 циклическим сдвигом s1, используя только один вызов метода isSubstring (пример: слово waterbottleполучено циклическим сдвигом erbottlewat).