Переверни его. Переверни наоборот / Песочница / Хабр

Пара слов о том, как программисты разных конфессий справляются с самой очевидной задачей в Computer Science.

А вы уверены, что хорошо понимаете все тонкости разворачивания списков?

Задача разворота связного списка до сих пор в десятке самых популярных на собеседованиях, и умудренные опытом джейсоноукладки разработчики наивно полагают, что подводных камней в ней уже давно не осталось. Ну что ж, давайте посмотрим, насколько там все очевидно.

Связный список. Связный, блин, список. Эта штука преследует программистов, как тени под глазами после ночного деплоя в пятницу. Каждый собеседующий на позицию «мы ищем рок-звезду» задает этот вопрос с видом человека, открывающего тебе тайны мироздания. Переверни список. Cправишься — будешь писать круды за еду. Не справишься — иди торговать шавермой, там интервью попроще.

Так вот: переворачивание списка — это лакмусовая бумажка для парадигмы. По тому, как язык программирования решает эту задачу, можно понять о нем примерно все. Включая то, какой сорт кофе предпочитает средний его адепт.

Erlang: телефонная станция решает школьную олимпиаду

Эрланг был создан для того, чтобы шведские телефонные станции работали как швейцарские часы. То, что на нем можно переворачивать списки — чистое совпадение. Как если бы танком открывали пивные бутылки: технически возможно, но инженеры Ericsson определенно имели в виду что-то другое.

reverse(List) -> reverse(List, []).
reverse([], Acc) -> Acc;
reverse([H|T], Acc) -> reverse(T, [H|Acc]).

Тут все честно. Два аргумента: список и аккумулятор. Берешь голову, кладешь в аккумулятор, хвост рекурсивно обрабатываешь. Когда список кончится — аккумулятор и есть результат. Хвостовая рекурсия, никаких фокусов. Ошибиться буквально негде: в эрланге нет циклов

Код выглядит так, будто его писал бухгалтер. Скучный, предсказуемый, работает уже тридцать лет без единого сбоя. Как шведская мебель. В стандартной библиотеке есть :lists.reverse/1.

Elixir: когда Erlang надел очки в роговой оправе

Эликсир — это Эрланг для людей, которые считают, что fun вместо fn — это излишняя многословность. Тот же BEAM, та же семантика, но теперь с пайпами и сахаром.

def reverse(list), do: reverse(list, [])
defp reverse([], acc), do: acc
defp reverse([h | t], acc), do: reverse(t, [h | acc])

Идентичная логика, немного иной синтаксис. В стандартной библиотеке, естественно, есть Enum.reverse/1.

В эрланге и эликсире допустить ошибку в этом коде довольно непросто, поэтому на собеседованиях по этим языкам списки переворачивать, как правило, не требуют. Не, можно, конечно, притащить стандартную библиотеку или comprehensions, но такое вряд ли придет в голову даже джуну.

Как не надо:

# std library
Enum.reduce(list, [], &[&1|&2])

# comprehension
for x <- list, reduce: [], do: (acc -> [x | acc])

А что у нас в языках с богатыми возможностями?

Haskell: функциональное высокомерие

Хаскель — это язык, на котором люди пишут статьи про языки, на которых можно писать. Монады, функторы, аппликативные функторы, моноиды. Если ты не понимаешь, что такое Monad, значит, ты недостаточно умен. Если понимаешь — все равно недостаточно умен, просто притворяешься лучше.

Как надо:

reverse :: [a] -> [a]
reverse = foldl (flip (:)) []

Одна строка. Используем foldl, переворачиваем оператор cons через flip, и вуаля. Элегантно, как смокинг.

Как не надо:

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

Тут квадратичная сложность из-за конкатенации списков (++), и любой хаскеллист посмотрит на вас как на человека, который режет пиццу ножницами.

Idris: ФП для тех, кому Haskell показался слишком практичным

Идрис — это зависимые типы. Это когда ты можешь доказать на уровне системы типов, что твой список действительно перевернут. Не просто «я написал тесты», а математически доказал. Компилятор — твой теорема-прувер.

Как надо:

Нужно доказательство, а не просто код. К сожалению, даже для такой простой задачи оно оказываетсядовольно громоздким (вот, например). Но если вы каким-то чудом оказались на собеседовании по Идрису, такой код — это единственный вариант.

Как не надо:

reverse : Vect n a -> Vect n a
reverse [] = []
reverse (x :: xs) = reverse xs ++ [x]

Тут компилятор хотя бы проверит, что длина вектора сохраняется, и если реализация случайно потеряет элемент — код просто не скомпилируется.

Как совсем не надо:

reverse : List a -> List a
reverse [] = []
reverse (x :: xs) = reverse xs ++ [x]

Ruby: язык, в котором все уже сделано за тебя

Без стандартной библиотеки имеет смысл сворачивать список с аккумулятором.

Как надо:

def reverse(list)
  list.reduce([]) { |result, item| result.unshift(item) }
end

Как не надо:

def reverse(list)
  result = []
  list.each { |item| result.unshift(item) }
  result
end

Мне лично приходилось заворачивать людей, которые расплескивают локальные переменные наружу скоупа и используют итерации вместо свёрток. Код выше настолько невыразителен, что любой профессионал на нём будет спотыкаться. Но это бы еще и ладно.

Как совсем не надо:

def reverse(list, memo = [])
  return memo if list == []
  reverse(list[1..-1], [list[0]] + memo)
end

Руби не предназначен для рекурсии. Но если уж так хочется показать именно рекурсивное решение, надо не забыть проинструктировать виртуальную машину не забывать про хвостовую оптимизацию, иначе код выше отыквится на сравнительно больших аргументах:

pry> reverse((1..42_000).to_a)
#⇒ SystemStackError: stack level too deep

Но:

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}
# необходимо переопределить метод, иначе VM не станет применять TCO 
def reverse(list, memo = [])
  return memo if list == []
  reverse(list[1..-1], [list[0]] + memo)
end
reverse((1..42_000).to_a)
#⇒ [42000, 41999, …]

JavaScript: хаос, возведенный в систему

JavaScript был написан за десять дней. И каждый из этих дней ощущается в любой строке кода.

Как надо:

const reverse = (list) => [...list].reverse();

Или, без стандартной библиотеки:

const reverse = (list) => list.reduce((acc, current) => [current, ...acc], []); ;

Как не надо:

const reverse = (list) => list.reverse();

Array.prototype.reverse() мутирует исходный массив, а в 2026 году это не самое ожидаемое поведение какой-то сторонней функции.

А spread-оператор создает копию. Теперь мы функциональные программисты. Почти. Если не смотреть слишком пристально.

Как совсем не надо:

const reverse = ([head, ...tail]) =>
  head === undefined ? [] : [...reverse(tail), head];

Деструктуризация, spread, рекурсия. Три модных слова в одной функции. HR будет в восторге. Вот только такой код отыквится еще быстрее, чем руби выше. И способа починить уже нет. В JS хвостовой оптимизации не бывает, а без нее любой рекурсивный вызов — переход пропасти по канату.

Как можно:

Если нельзя пользоваться стандартной библиотекой, у нас все еще есть циклы.

function reverse(arr) {
  let reversed = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    reversed.push(arr[i]);
  }
  return reversed;
}

Python: читаемость прежде всего (и после всего тоже)

Как надо:

def reverse(lst):
    return lst[::-1]

Слайсы. [::-1] — это «от начала до конца с шагом минус один». Криптография? Нет, просто читаемость кода важнее всего остального.

Как не надо:

def reverse(lst):
    result = []
    for item in lst:
        result.insert(0, item)
    return result

Императивно, понятно, квадратичная сложность из-за insert(0, ...). Зато любой джун прочитает. А это важнее всего.

Как совсем не надо:

def reverse(lst):
    if not lst:
        return []
    return reverse(lst[1:]) + [lst[0]]

На больших списках упадет с RecursionError. Python не оптимизирует хвостовую рекурсию принципиально. Гвидо так решил, и мы живем с этим.

Как можно:

from functools import reduce

def reverse(lst):
    return reduce(lambda acc, x: [x] + acc, lst, [])

Как можно:

def reverse(lst):
    return [lst[i] for i in range(len(lst) - 1, -1, -1)]

Как можно, но не нужно:

def reverse(lst):
    result = []
    for i in range(len(lst) - 1, -1, -1):
        result.append(lst[i])
    return result

Go: простота как форма агрессии

Go — это язык, созданный в Google. Циклы и структуры, чтобы не перегреть голову гуглерам.

Как надо:

С дженериками (теперь они есть):

func reverse[T any](list []T) []T {
    result := make([]T, len(list))
    for i, v := range list {
        result[len(list)-1-i] = v
    }
    return result
}

Никакой магии. Создаем слайс нужного размера, заполняем в обратном порядке. Как в учебнике по программированию 1985 года. Но быстро.

Как не надо:

func reverse[T any](list []T) {
    for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 {
        list[i], list[j] = list[j], list[i]
    }
}

Это быстрее варианта выше, но пользователям кода навряд ли понравится, что список изменяется по месту.

Как хотелось бы:

reduce — не предусмотрен в стандартной библиотеке;
comprehensions — не предусмотрены в стандартной библиотеке;
рекурсия — TCO не предусмотрен в стандартной библиотеке, поэтому нет.

Rust: параноидальная безопасность

Rust — это язык для людей, которые просыпаются в холодном поту от мысли о dangling pointer. Компилятор Rust — строгий учитель, который бьет по рукам за каждую потенциальную ошибку. Но потом твой код работает. Без segfault. Без утечек памяти. Без надежды на лучшую жизнь, потому что ты потратил её на борьбу с borrow checker.

Как надо:

fn reverse<T>(list: Vec<T>) -> Vec<T> {
    list.into_iter().rev().collect()
}

into_iter() забирает владение, rev() переворачивает итератор, collect() собирает обратно в вектор. Функционально, элегантно, zero-cost abstraction.

Как можно:

Выше я везде помечал изменения по месту маркером «как не надо», но в расте это — приелемый и осмысленный вариант, специфика языка готовит пользователя кода к тому, что вся эволюция происходит по месту.

fn reverse<T>(list: &mut Vec<T>) {
    list.reverse();
}

Мутабельная ссылка. &mut. Компилятор проверит, что никто больше не держит ссылку на этот вектор. Если держит — не скомпилируется.

Как надо для связного списка (настоящего, не вектора):

fn reverse<T>(mut list: LinkedList<T>) -> LinkedList<T> {
    let mut result = LinkedList::new();
    while let Some(item) = list.pop_front() {
        result.push_front(item);
    }
    result
}

LinkedList в стандартной библиотеке Rust — редкий зверь. Все используют Vec, потому что кэш процессора важнее алгоритмической чистоты.

C, C++

Как не надо:

Писать свою функцию.

Как надо:

Возьмите готовую реализацию из сторонней библиотеки, интернета, LLM-ки.

Java, C#, и т. п.

В энтерпрайзах списки не разворачивают.

Эпилог: к чему это всё?

В принципе, ничего нового. Функциональные языки рекурсивно складывают в аккумулятор. Императивные — итерируют и мутируют. Мультипарадигменные — делают и то, и другое, и еще что-нибудь странное. И, тем не менее, я надеюсь, что этот текст немного расширил горизонты вашей эрудиции.

Суть в том, что переворачивание списка — это не про списки. Это про мировоззрение. Хаскеллист видит fold. Гофер видит цикл. Рубист видит один вызов метода и идет пить чай.

А интервьюер видит, как ты потеешь у доски, и тихо радуется, что сегодня не его очередь.

P.S. Если вы дочитали до сюда и всё ещё не знаете, как перевернуть связный список — используйте стандартную библиотеку. Для того она и существует.