Mediumlinked-list
Как реализовать разворот односвязного списка?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 206. Разворот через три указателя: prev, head (текущий), nxt (временный). На каждой итерации меняем направление указателя. O(n) время, O(1) память.
def reverseList(head):
prev = None
while head:
nxt = head.next # сохранить следующий
head.next = prev # развернуть указатель
prev = head # сдвинуть prev
head = nxt # сдвинуть head
return prev # новая головаРекурсивный вариант — O(n) время, O(n) стек: дойти до конца, на обратном пути каждый узел указывает на предшественника (head.next.next = head). Вариации: reverse between m and n (LeetCode 92), reverse in k-groups (LeetCode 25).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.