Сегодня мы работаем над 206. Обратно связанный список

Учитывая head односвязного списка, переверните список и верните обратный список.

Это классическая проблема обратно связанного списка.

Сама проблема не требует пояснений, и нам не нужно ничего указывать, кроме чего-то вроде:

  1. сколько узлов в списке? Есть ли что-то большее, чем то, что мы можем хранить в памяти?
  2. Имеет ли значение тип значения, хранящегося в узле?

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

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

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

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 вещами:

  1. текущий узел, на котором мы работаем (назовем его cur)
  2. предыдущий узел, который указывает на текущий узел как на следующий (prev)
  3. следующий узел для текущего (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 для графа). Как убедиться, что вы можете реверсировать один без потери ссылки на другую?

Вот и все! Еще одна проблема вниз.