0Pricing
DSA Interview Prep · Lekcja

Odwracanie listy jednokierunkowej

Odwrócą Państwo jednokierunkową listę iteracyjnie, przepinając trzy wskaźniki, oraz rekurencyjnie, śledząc każdy krok na diagramie w stylu tablicy.

Odwracanie listy jednokierunkowej to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Dlaczego odwracanie listy jest tak ważne

Odwracanie listy wiązanej należy do najczęściej zadawanych pytań podczas rozmów kwalifikacyjnych dotyczących programowania. Sprawdza umiejętność precyzyjnego manipulowania wskaźnikami bez utraty dostępu do węzłów. Różne warianty tego zadania występują zarówno jako samodzielne problemy, jak i jako etapy większych algorytmów, takich jak wykrywanie palindromu, porządkowanie listy czy odwracanie grupami po k elementów.

Podejście iteracyjne wykorzystuje trzy wskaźniki: prev, curr i next_node. Podejście rekurencyjne wyraża tę samą logikę jako przejście z wykorzystaniem stosu wywołań. Oba podejścia działają w czasie O(n), a podejście iteracyjne wymaga O(1) pamięci.

Iteracyjne odwracanie za pomocą trzech wskaźników

W każdym kroku iteracyjnego odwracania należy: zapisać curr.next, aby nie utracić reszty listy, odwrócić curr.next, tak aby wskazywał wstecz na prev, przesunąć prev na curr, a następnie przesunąć curr na zapisany następny węzeł. Gdy curr stanie się None, pętla się kończy, a prev jest nową głową listy.

Przydatne hasło ułatwiające zapamiętanie kolejności: Zapisz, Odwróć, Przesuń, Przesuń.

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

Śledzenie krok po kroku

Prześledźmy działanie reverse_list dla 1 -> 2 -> 3. Początkowo prev=None, curr=1. Krok 1: zapisz next=2, odwróć 1.next=None, prev=1, curr=2. Krok 2: zapisz next=3, odwróć 2.next=1, prev=2, curr=3. Krok 3: zapisz next=None, odwróć 3.next=2, prev=3, curr=None. Pętla się kończy; zwróć prev=3, który jest nową głową listy 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

Rekurencyjne odwracanie

Podejście rekurencyjne zakłada, że reverse_list(head.next) zwraca nową głowę już odwróconego sufiksu. Pozostaje odwrócić wskaźnik między head a head.next: ustaw head.next.next = head (skieruj dawny drugi węzeł z powrotem do pierwszego) oraz head.next = None (przerwij stare połączenie w przód). Nowa głowa jest zwracana z przypadku bazowego.

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

Odwracanie podlisty (LeetCode 92)

LeetCode 92 „Reverse Linked List II” wymaga odwrócenia podlisty od pozycji left do right (numerowanych od 1) w jednym przebiegu. Sztuczka polega na znalezieniu węzła poprzedzającego podlistę (należy użyć fikcyjnego węzła początkowego, aby było to zawsze możliwe), a następnie wykonaniu odwracania za pomocą trzech wskaźników dokładnie przez (right - left) kroków i ponownym połączeniu odwróconego segmentu z resztą listy.

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

Odwracanie węzłów w grupach po k (LeetCode 25)

LeetCode 25 „Reverse Nodes in k-Group” odwraca każdą kolejną grupę k węzłów. Należy sprawdzić, czy pozostało k węzłów; jeśli nie, należy pozostawić je bez zmian. Następnie trzeba odwrócić kolejne k węzłów metodą iteracyjną, rekurencyjnie odwrócić pozostałą listę i połączyć ją z odwróconym fragmentem. Złożoność czasowa nadal wynosi O(n), a głębokość rekurencyjnych wywołań 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

Lista wiązana będąca palindromem

LeetCode 234 „Palindrome Linked List”: sprawdzenie, czy lista wiązana jest palindromem, w czasie O(n) i przy użyciu O(1) pamięci. Strategia: znajdź punkt środkowy za pomocą wolnego i szybkiego wskaźnika, odwróć drugą połowę w miejscu, porównaj obie połowy węzeł po węźle, a następnie opcjonalnie przywróć listę. Łączy to znajdowanie punktu środkowego i odwracanie — dwie podstawowe umiejętności.

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

Porównanie podejścia iteracyjnego i rekurencyjnego

Iteracyjne odwracanie używa O(1) pamięci i jest zazwyczaj preferowane. Rekurencyjne odwracanie wymaga O(n) pamięci stosu ze względu na głębokość wywołań, co może spowodować przepełnienie stosu dla bardzo długich list (domyślny limit języka Python wynosi około 1000 poziomów rekurencji).

Podczas rozmowy rekrutacyjnej należy najpierw zaimplementować wersję iteracyjną, aby pokazać znajomość ograniczeń pamięci, a następnie wspomnieć o wersji rekurencyjnej jako prostszej alternatywie, jeśli długość listy jest ograniczona.

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)

Częste błędy przy odwracaniu

Trzy błędy odpowiadają za niemal wszystkie problemy z odwracaniem. Po pierwsze, niezapisanie next przed nadpisaniem: curr.next = prev niszczy odwołanie do dalszej części listy, jeśli wcześniej nie zapisano next_node. Po drugie, niezwrócenie prev: na końcu pętli curr ma wartość None, ale prev jest nową głową. Po trzecie, nieprawidłowy przypadek bazowy rekurencji: pominięcie not head.next oznacza, że lista jednoelementowa nie jest obsługiwana i powoduje błąd 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

Przeorganizowanie listy (LeetCode 143)

LeetCode 143 „Reorder List” przekształca L0 → L1 → L2 → ... → Ln w L0 → Ln → L1 → Ln-1 → L2 → Ln-2 w czasie O(n) i przy użyciu O(1) pamięci. Rozwiązanie łączy trzy kroki: znalezienie punktu środkowego, odwrócenie drugiej połowy oraz przeplatanie obu połówek. Opanowanie odwracania sprawia, że ten pozornie złożony problem staje się prostym połączeniem znanych narzędzi.

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

Podsumowanie: odwracanie jako element budulcowy

Odwracanie listy wiązanej rzadko jest celem samym w sobie — stanowi element budulcowy. Wykrywanie palindromu, odwracanie grup po k, przeorganizowanie listy oraz odwracanie między pozycjami opierają się na tym samym iteracyjnym wzorcu z trzema wskaźnikami. Gdy wzorzec stanie się automatyczny, można skupić uwagę na strukturze problemu wyższego poziomu.

Należy zawsze ćwiczyć odwracanie, aż będzie można napisać je z pamięci w mniej niż dwie minuty; w jakiejś postaci pojawi się ono podczas niemal każdej rozmowy rekrutacyjnej dotyczącej list wiązanych.

Szybkie sprawdzenie

Sprawdź, czy rozumiesz pojęcia z kursu Data Structures & Algorithms — Coding Interview Prep omówione w tej lekcji.

Podsumowanie lekcji

W tej lekcji omówiono: iteracyjny wzorzec Zapisz-Odwróć-Przesuń-Przesuń odwraca listę w czasie O(n) i przy użyciu O(1) pamięci, podejście rekurencyjne zakłada, że sufiks jest już odwrócony, i poprawia tylko ostatnie połączenie oraz odwracanie jest podstawowym krokiem wykrywania palindromu, przeorganizowywania listy i odwracania grup po k. Następnie omówimy wykrywanie cykli za pomocą algorytmu Floyda.

Często zadawane pytania

Czy lekcja „Odwracanie listy jednokierunkowej” jest bezpłatna?

Tak — pełny tekst „Odwracanie listy jednokierunkowej” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Odwracanie listy jednokierunkowej”?

Odwrócą Państwo jednokierunkową listę iteracyjnie, przepinając trzy wskaźniki, oraz rekurencyjnie, śledząc każdy krok na diagramie w stylu tablicy. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?

Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Odwracanie listy jednokierunkowej”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?

Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Klasa Node i tworzenie listy
  2. Odwracanie listy jednokierunkowej
  3. Wykrywanie cyklu algorytmem Floyda
  4. Scalanie, dzielenie i znajdowanie n-tego elementu od końca
← Powrót do DSA Interview Prep