0Pricing
DSA Interview Prep · Урок

Разворот связного списка

Разверните односвязный список итеративно с перенастройкой трёх указателей и рекурсивно, отслеживая каждый шаг на схеме в стиле работы у доски

«Разворот связного списка» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Почему разворот списка необходим

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

Итеративный подход использует три указателя: prev, curr и next_node. Рекурсивный подход выражает ту же логику в виде обхода стека вызовов. Оба подхода работают за O(n), а итеративный требует O(1) дополнительной памяти.

Итеративный разворот с тремя указателями

На каждом шаге итеративного разворота сохраните curr.next, чтобы не потерять оставшуюся часть списка, измените curr.next так, чтобы он указывал назад на prev, переместите prev на curr, а curr — на сохранённый следующий узел. Когда curr станет равен None, цикл завершится, а prev станет новой головой списка.

Полезная мнемоника: Сохранить, развернуть, продвинуть, продвинуть.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node  = curr.next   # Save
        curr.next  = prev        # Flip
        prev       = curr        # Advance prev
        curr       = next_node   # Advance curr
    return prev  # new head

# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
    print(head.val, end=' ')  # 5 4 3 2 1
    head = head.next

Пошаговая трассировка

Проследим работу reverse_list на списке 1 -> 2 -> 3. Изначально prev=None, curr=1. Шаг 1: сохраняем next=2, меняем направление указателя 1.next на None, prev=1, curr=2. Шаг 2: сохраняем next=3, меняем направление указателя 2.next на 1, prev=2, curr=3. Шаг 3: сохраняем next=None, меняем направление указателя 3.next на 2, prev=3, curr=None. Цикл завершается; возвращаем prev=3 — это новая голова списка 3 -> 2 -> 1.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list_traced(head):
    prev, curr = None, head
    step = 0
    while curr:
        step += 1
        next_node = curr.next
        curr.next = prev
        print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
        prev = curr
        curr = next_node
    return prev

nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val)  # 3

Рекурсивный разворот

Рекурсивный подход предполагает, что reverse_list(head.next) возвращает новую голову уже развернутого хвоста. Остается только изменить направление указателя между head и head.next: установить head.next.next = head (направить старый второй узел обратно на старый первый) и head.next = None (разорвать старую прямую связь). Новая голова поднимается из базового случая по цепочке возвратов.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list_rec(head):
    # Base case: empty or single node
    if not head or not head.next:
        return head
    new_head = reverse_list_rec(head.next)  # reverse suffix
    head.next.next = head   # former second node points back
    head.next = None        # sever forward link
    return new_head

nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
    print(head.val, end=' ')  # 4 3 2 1
    head = head.next

Разворот подсписка (LeetCode 92)

В задаче LeetCode 92 «Reverse Linked List II» требуется развернуть подсписок с позиции left по позицию right (нумерация начинается с 1) за один проход. Секрет в том, чтобы найти узел перед подсписком (используйте фиктивную голову, чтобы этот узел существовал всегда), затем выполнить разворот с тремя указателями ровно (right - left) раз и, наконец, соединить развернутый сегмент с окружающей частью списка.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(head, left, right):
    dummy = ListNode(0, head)
    pre = dummy
    # Advance pre to node just before position 'left'
    for _ in range(left - 1):
        pre = pre.next
    curr = pre.next
    for _ in range(right - left):
        next_node   = curr.next
        curr.next   = next_node.next
        next_node.next = pre.next
        pre.next    = next_node
    return dummy.next

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
    print(head.val, end=' ')  # 1 4 3 2 5
    head = head.next

Разворот узлов группами по k (LeetCode 25)

В задаче LeetCode 25 «Reverse Nodes in k-Group» каждая последовательная группа из k узлов разворачивается. Подход таков: проверьте, осталось ли k узлов; если нет, оставьте их без изменений. Разверните следующие k узлов итеративным методом, затем рекурсивно разверните оставшийся список и соедините его с первой частью. Временная сложность остается равной O(n), а глубина рекурсивных вызовов — O(n/k).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    # Check if k nodes are available
    curr, count = head, 0
    while curr and count < k:
        curr = curr.next
        count += 1
    if count < k:
        return head   # fewer than k nodes left, keep as-is
    # Reverse k nodes
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # head is now the tail of the reversed group
    head.next = reverseKGroup(curr, k)
    return prev

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
    print(head.val, end=' ')  # 2 1 4 3 5
    head = head.next

Связный список-палиндром

LeetCode 234 «Palindrome Linked List»: проверьте, является ли связный список палиндромом, за время O(n) и с дополнительной памятью O(1). Стратегия: найдите середину с помощью медленного и быстрого указателей, разверните вторую половину на месте, сравните две половины узел за узлом, а затем при необходимости восстановите список. Здесь объединяются поиск середины и разворот — два базовых навыка.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    # Find mid
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Compare
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left  = left.next
        right = right.next
    return True

def build(arr):
    d = ListNode(0)
    c = d
    for v in arr:
        c.next = ListNode(v)
        c = c.next
    return d.next

print(isPalindrome(build([1,2,2,1])))  # True
print(isPalindrome(build([1,2,3])))    # False

Сравнение итеративного и рекурсивного подходов

Итеративный разворот использует память O(1) и обычно является предпочтительным. Рекурсивный разворот использует память стека O(n) из-за глубины вызовов, что может привести к переполнению стека для очень длинных списков (ограничение Python по умолчанию составляет около 1000 уровней рекурсии).

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

import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint

# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)

Распространенные ошибки при развороте

Почти все ошибки при развороте связаны с тремя причинами. Во-первых, не сохранено значение next перед перезаписью: curr.next = prev уничтожает ссылку вперед, если значение next_node не было сохранено. Во-вторых, не возвращается prev: в конце цикла curr равен None, а prev — это новая голова. В-третьих, неверный базовый случай рекурсии: если забыть not head.next, список из одного узла не будет обработан и возникнет ошибка AttributeError.

# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next   # BUG if omitted: lose rest of list
        curr.next = prev
        prev      = curr
        curr      = next_node
    return prev               # BUG if you return curr: it is None

nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
    print(h.val, end=' ')  # 3 2 1
    h = h.next

Перестановка списка (LeetCode 143)

Задача LeetCode 143 «Reorder List» перестраивает L0 → L1 → L2 → ... → Ln в L0 → Ln → L1 → Ln-1 → L2 → Ln-2 за время O(n) и с дополнительной памятью O(1). Решение объединяет три шага: найти середину, развернуть вторую половину и чередовать узлы двух половин. Освоив разворот, вы превращаете эту на первый взгляд сложную задачу в простое сочетание знакомых инструментов.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    # Find mid
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Interleave
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
    print(h.val, end=' ')  # 1 4 2 3
    h = h.next

Итоги: разворот как строительный блок

Разворот связного списка редко является конечной целью — это строительный блок. Обнаружение палиндрома, разворот групп по k, перестановка списка и разворот между позициями основаны на одном и том же итеративном шаблоне с тремя указателями. Когда этот шаблон становится автоматическим, вы можете сосредоточить внимание на структуре задачи более высокого уровня.

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

Быстрая проверка

Проверьте свое понимание концепций «Структуры данных и алгоритмы — подготовка к техническому собеседованию» из этого урока.

Итоги урока

В этом уроке вы узнали, что итеративный шаблон «Сохранить — развернуть — перейти — перейти» разворачивает список за время O(n) и с дополнительной памятью O(1), рекурсивный подход предполагает, что хвост уже развернут, и исправляет только последнюю связь, а разворот — это ключевой подшаг при обнаружении палиндрома, перестановке списка и развороте групп по k. Далее мы рассмотрим обнаружение циклов с помощью алгоритма Флойда.

Часто задаваемые вопросы

Урок «Разворот связного списка» бесплатный?

Да — полный текст урока «Разворот связного списка» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Разворот связного списка»?

Разверните односвязный список итеративно с перенастройкой трёх указателей и рекурсивно, отслеживая каждый шаг на схеме в стиле работы у доски Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Разворот связного списка»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Класс узла и построение списка
  2. Разворот связного списка
  3. Обнаружение циклов алгоритмом Флойда
  4. Слияние, разделение и поиск с конца
← Назад к DSA Interview Prep