Сегодня мы работаем над 206. Обратно связанный список
Учитывая
head
односвязного списка, переверните список и верните обратный список.
Это классическая проблема обратно связанного списка.
Сама проблема не требует пояснений, и нам не нужно ничего указывать, кроме чего-то вроде:
- сколько узлов в списке? Есть ли что-то большее, чем то, что мы можем хранить в памяти?
- Имеет ли значение тип значения, хранящегося в узле?
Мы задаем первый вопрос, потому что, если мы решим хранить все значения в списке, нам нужно убедиться, что мы можем это сделать. Второй вопрос заключается в том, чтобы убедиться, что мы имеем дело с числами.
Если интервьюер скажет нам, что мы можем хранить все значения, а значения — это просто числа, то мы можем продолжить.
Первый подход заключается в простом грубом переборе путем сохранения всех значений и создания другого списка.
def reverseList(head): if not head: return values = [] # first we store all values in order while head: values.append(head.val) head = head.next # next we create another linked list but reverse the values reverse_list = ListNode(values.pop()) head = reverse_list while values: reverse_list.next = ListNode(values.pop()) reverse_list = reverse_list.next return head
Какова временная сложность для этого?
Мы проходим по списку дважды, один раз для хранения значений, а другой для построения второго, обратно связанного списка, поэтому общая временная сложность составляет O(n), где n — длина связанного списка.
Это работает, но недостаточно элегантно. Можем ли мы переворачивать список на месте каждый раз, когда переходим к следующему узлу?
Нам нужно следить за 3 вещами:
- текущий узел, на котором мы работаем (назовем его
cur
) - предыдущий узел, который указывает на текущий узел как на следующий (
prev
) - следующий узел для текущего (
next_node
)
Мы хотим указать .next
для cur
на prev
, но мы пока не можем потерять ссылку на cur.next
, поэтому мы обозначаем для этого next_node
перед повторной ссылкой cur.next
на prev
.
После этого мы делаем наш cur
новым prev
, а наш next_node
новым cur
. Затем мы продолжаем тот же процесс, пока не перестанем видеть cur
.
Не забывайте, что нам нужно инициализировать наш prev
до None
, так как ничто не имеет .next
для нашего первого узла.
Код будет выглядеть так:
def reverseList(head): prev = None cur = head # we can simply use head as variable but let's make it more clear while cur: next_node = cur.next cur.next = prev prev = cur cur = next_node return prev # the cur at this point is a None and the prev holds the last node
Если у вас есть проблемы с визуализацией этого, лучший способ увидеть это — запустить несколько примеров. Следите за prev
, cur
и next_node
. Если вы используете стрелки для представления next
, вы увидите, как стрелки начинают переворачиваться по мере того, как вы перебираете список.
Какова временная сложность этого подхода? Мы по-прежнему видим O(n), потому что нам все еще нужно просмотреть весь список, но мы экономим память, потому что нам не нужно сначала сохранять все значения в списке. В то же время мы сэкономили немного времени (хотя Big O не изменилась), потому что нам нужно пройти по списку только один раз.
Есть ли другой способ решить эту проблему?
Мы справились с этим в итеративном подходе, используя цикл while. Мы предпринимаем одни и те же действия в каждой итерации. Это похоже на работу, которую мы также можем реализовать рекурсивным способом.
Как преобразовать итеративное решение в рекурсивное? Рекурсивные подходы всегда состоят из базового случая и рекурсивного алгоритма.
Наш базовый случай — просто когда мы больше не видим узел, то есть у нас нет cur
. Наш рекурсивный алгоритм — это то, что мы сделали в цикле while.
Для этого мы можем использовать вспомогательную функцию:
def helper(cur, prev): # base case if not cur: return prev next_node = cur.next cur.next = prev # we simplify "prev = cur" and "cur = next_node" into the input args here return helper(next_node, cur)
Затем наша корневая функция просто вызывает помощника, в результате чего общий код выглядит так:
def helper(cur, prev): # base case if not cur: return prev next_node = cur.next cur.next = prev # we simplify "prev = cur" and "cur = next_node" into the input args here return helper(next_node, cur) def reverseList(head): return helper(head, None) # first prev is None
Временная сложность по-прежнему составляет O(n), так как нам все еще нужно один раз пройти по связанному списку.
Если вы больше знакомы с рекурсией, не стесняйтесь использовать этот подход, но лично мне нравится итеративный подход к этому вопросу.
Это простая задача для проверки способности кандидатов распознавать, какие шаги нужно предпринять, чтобы изменить список и как отслеживать каждый компонент. Что еще более важно, он проверяет способность кандидатов разбивать проблему на более мелкие компоненты и способность работать с каждым компонентом.
В противном случае это очень простая проблема. Я не вижу, чтобы крупные технические специалисты использовали эту проблему для тестирования (но если по какой-то причине они это сделают, это ваш счастливый день), но небольшие фирмы используют это, когда хотят нанять младших сотрудников, просто чтобы убедиться, что кандидаты умеют программировать.
И последнее, что реверсирование связанного списка на самом деле не является тривиальным в реальной жизни, хотя большую часть времени это делается в виде графиков (скажем, вы хотите реверсировать DAG для графа). Как убедиться, что вы можете реверсировать один без потери ссылки на другую?
Вот и все! Еще одна проблема вниз.