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

В этом посте я хотел обсудить один из самых популярных вопросов, которые возникают в технических интервью: как перевернуть связанный список. Я буду использовать Swift 3 для написания кода.

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

Даже с этими ограничениями связанные списки составляют основу многих функциональных языков. Я действительно удивлен, что Swift до сих пор не получил нативной реализации этой важной структуры данных.

Связанный список может быть определен как: 1) пустой список или 2) элемент заголовка, за которым следует хвост, который сам по себе является связанным списком. Это определение в терминах альтернатив делает перечисление естественным способом реализации связанного списка в Swift.

public enum LinkedList<Element> {
  case empty
  indirect case list(Element, LinkedList<Element>)
}

И это все, что нужно для разработки идеально функциональной структуры данных связанного списка в Swift!

Теперь, когда у нас есть определенная структура данных, пришло время написать функцию для реверсирования данного связанного списка.

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

public func reversed() -> LinkedList<Element> {
  func reversed(input: LinkedList<Element>,
        output: LinkedList<Element>) -> LinkedList<Element> {
    switch input {
    case .empty:
      return output
    case let .list(head, tail):
      return reversed(input: tail, output: .list(head, output))
    }
  }
  return reversed(input: self, output: .empty)
}

Менее чем через дюжину строк кода мы теперь можем перевернуть связанный список.

Теперь давайте напишем небольшой тест, чтобы убедиться, что код действительно может выполнить то, что мы обещали. Вот код, который создаст связанный список с числами от 1 до 4, перевернет его, а затем использует сопоставление с образцом, чтобы убедиться, что список был перевернут правильно.

let foo = LinkedList.list(1, .list(2, .list(3, .list(4, .empty))))
let oof = foo.reversed()
switch oof {
case .list(4, .list(3, .list(2, .list(1, .empty)))):
  print("Reversed!")
default:
  print("Oops.")
}

Теперь вы можете создать структуру данных для представления связанного списка, написать функцию для переворота связанного списка и продемонстрировать некоторые знания о расширенных функциях Swift на этом пути.