Задачи на связные списки

Большинство задач на связные списки решается несколькими приёмами: перестановка указателей next, два указателя (медленный/быстрый или с разрывом) и фиктивная голова (dummy head). Класс Node знаком по теме о связных списках: Node(value, next).

Вспомогательные функции

Для тестов удобно строить список из массива и превращать его обратно.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def build(items):
    head = None
    for v in reversed(items):
        head = Node(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

print(to_list(build([1, 2, 3])))

[1, 2, 3]

Разворот списка

Держим три указателя: prev (голова уже развёрнутой части), head (текущий узел) и nxt (следующий узел, который нельзя потерять). На каждом шаге направляем head.next на prev. Время O(n), память O(1).

def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

print(to_list(reverse(build([1, 2, 3, 4]))))
print(to_list(reverse(None)))

[4, 3, 2, 1]
[]

💡 Строку nxt = head.next нужно писать до head.next = prev, иначе остаток списка потеряется.

Середина: медленный и быстрый указатель