Задача: найти центральный элемент односвязного списка

Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня ищем центральный элемент односвязного списка.

Иллюстрация: Polina Vari для Skillbox Media

Дмитрий Зверев

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Сергей Голицын

Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.

Условие. Дана голова односвязного списка — head. Необходимо вернуть его центральный элемент и все остальные элементы после него. Если в списке два центральных элемента, то вернуть второй и все элементы за ним.

Пояснение. Связный список — это список из объектов, которые связаны друг с другом. Каждый элемент состоит из двух компонентов: собственно данных и ссылки на следующий элемент. Головой (head) связного списка называют его первый элемент. Конечный элемент — это хвост. Главное отличие хвоста от остальных элементов в том, что его ссылка на следующий элемент — это null.

Ввод и вывод. Пример 1

Ввод: head = [1,2,3,4,5]
Вывод: [3,4,5]
Пояснение: центральный элемент — 3.

Пример 2

Ввод: head = [1,2,3,4,5,6]
Вывод: [4,5,6]
Пояснение: так как центральных элементов два — 3 и 4, мы возвращаем второй из них — 4.

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

Эта задача может быть немного каверзной. Но мы разберём два возможных решения.

Самым простым решением будет проитерировать весь список и посчитать количество элементов, а затем найти индекс центрального и вернуть его. Очень просто.

Второе решение чуть сложнее. Мы будем использовать способ с двумя указателями — медленным и быстрым. Оба будут пробегать по всему списку, пока не достигнут конца. А конец в нашем случае — это один из двух вариантов: первый — список имеет цикл, и бегунки встретятся, второй — мы будем иметь null в конце списка.

Пояснение: список будет зациклен, если его хвостовой элемент указывает не на null, а на индекс другого элемента. Получается, что мы будем бесконечно перебирать элементы списка и никогда не достигнем его конца.

Когда быстрый указатель достигнет конца, медленный будет как раз в середине списка.

При этом не стоит забывать и о границах списка. Мы должны проверять быстрый указатель, чтобы элемент, на который он указывает в текущий момент, и следующий за ним элемент не были равны null.

Давайте реализуем это в коде:

public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }

Результаты

Временная сложность: O(n) — так как мы однократно проходимся по всему массиву.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.

Читайте также: