0Pricing
Coding Interview Prep · Lezione

Invertire una linked list

Inverta iterativamente una lista concatenata semplice riconfigurando tre puntatori e lo faccia ricorsivamente, tracciando ogni passaggio su un diagramma in stile lavagna

Invertire una linked list è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.

Perché l'inversione di una lista è fondamentale

L'inversione di una lista concatenata è una delle domande più frequenti nei colloqui tecnici di programmazione. Mette alla prova la capacità di manipolare con precisione i puntatori senza perdere il riferimento ai nodi. Le varianti compaiono sia come problemi autonomi sia come passaggi secondari di algoritmi più complessi, come il rilevamento dei palindromi, il riordinamento di una lista e l'inversione a gruppi di k elementi.

L'approccio iterativo usa tre puntatori: prev, curr e next_node. L'approccio ricorsivo esprime la stessa logica attraverso l'attraversamento dello stack delle chiamate. Entrambi raggiungono un tempo O(n); la versione iterativa usa spazio O(1).

Inversione iterativa con tre puntatori

A ogni passaggio dell'inversione iterativa: salvare curr.next per non perdere il resto della lista, invertire curr.next in modo che punti all'indietro verso prev, far avanzare prev fino a curr e far avanzare curr fino al next salvato. Quando curr diventa None, il ciclo termina e prev è la nuova testa.

Un utile promemoria: Salva, inverti, avanza, avanza.

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

Tracciamento passo per passo

Tracciamo reverse_list su 1 -> 2 -> 3. Inizialmente prev=None, curr=1. Passo 1: salviamo next=2, invertiamo 1.next=None, prev=1, curr=2. Passo 2: salviamo next=3, invertiamo 2.next=1, prev=2, curr=3. Passo 3: salviamo next=None, invertiamo 3.next=2, prev=3, curr=None. Il ciclo termina; restituiamo prev=3, che è la nuova testa di 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

Inversione ricorsiva

L'approccio ricorsivo si basa sul fatto che reverse_list(head.next) restituisca la nuova testa del suffisso già invertito. Non resta che invertire il puntatore tra head e head.next: impostare head.next.next = head (per fare puntare il vecchio secondo nodo al vecchio primo) e head.next = None (per interrompere il vecchio collegamento in avanti). La nuova testa risale a partire dal caso base.

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

Invertire una sottolista (LeetCode 92)

LeetCode 92, «Reverse Linked List II», richiede di invertire la sottolista dalla posizione left alla posizione right (indicizzate a partire da 1) con una sola scansione. Il punto chiave consiste nel trovare il nodo precedente alla sottolista (utilizzando una testa fittizia, in modo che il nodo sia sempre valido), eseguire l'inversione con tre puntatori per esattamente (right - left) passi e infine ricollegare il segmento invertito al resto della lista.

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

Invertire i nodi in gruppi di k (LeetCode 25)

LeetCode 25, «Reverse Nodes in k-Group», inverte ogni gruppo consecutivo di k nodi. L'approccio è il seguente: verificare se rimangono k nodi; in caso contrario, lasciarli invariati. Invertire i k nodi successivi con il metodo iterativo, quindi invertire ricorsivamente la parte restante della lista e collegarla. La complessità temporale rimane O(n), con una profondità delle chiamate ricorsive pari 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 concatenata palindroma

LeetCode 234, «Palindrome Linked List»: verificare se una lista concatenata è palindroma in O(n) di tempo e O(1) di spazio. Strategia: trovare il punto centrale con i puntatori lento e veloce, invertire sul posto la seconda metà, confrontare le due metà nodo per nodo e infine, facoltativamente, ripristinare la lista. In questo modo si combinano la ricerca del punto centrale e l'inversione, due competenze fondamentali.

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

Confronto tra approccio iterativo e ricorsivo

L'inversione iterativa utilizza O(1) di spazio ed è generalmente preferibile. L'inversione ricorsiva utilizza O(n) di spazio nello stack a causa della profondità delle chiamate, che può causare un overflow dello stack per liste molto lunghe (il limite predefinito di Python è di circa 1000 livelli di ricorsione).

In un colloquio, implementi prima la versione iterativa per dimostrare di tenere conto dei vincoli di spazio, quindi menzioni la versione ricorsiva come alternativa più semplice se la lunghezza della lista è limitata.

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)

Errori comuni nell'inversione

Tre errori sono responsabili di quasi tutti i bug nelle inversioni. Primo: non salvare next prima di sovrascriverlo: curr.next = prev distrugge il riferimento in avanti se next_node non è stato salvato. Secondo: non restituire prev: al termine del ciclo, curr è None, mentre prev è la nuova testa. Terzo: caso base ricorsivo errato: dimenticare not head.next impedisce di gestire una lista con un solo nodo e causa un 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

Riordinare la lista (LeetCode 143)

LeetCode 143, «Reorder List», riorganizza L0 → L1 → L2 → ... → Ln in L0 → Ln → L1 → Ln-1 → L2 → Ln-2 in O(n) di tempo e O(1) di spazio. La soluzione combina tre passaggi: trovare il punto centrale, invertire la seconda metà e intrecciare le due metà. Padroneggiare l'inversione rende questo problema apparentemente complesso una combinazione lineare di strumenti già noti.

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

Riepilogo: l'inversione è un elemento fondamentale

L'inversione di una lista concatenata raramente è l'obiettivo finale: è un elemento fondamentale. Il rilevamento dei palindromi, l'inversione in gruppi di k, il riordinamento della lista e l'inversione tra due posizioni si basano tutti sullo stesso schema iterativo con tre puntatori. Quando lo schema diventa automatico, è possibile concentrare le proprie energie mentali sulla struttura del problema di livello superiore.

Si eserciti sempre sull'inversione finché non riuscirà a scriverla a memoria in meno di due minuti; apparirà in qualche forma in quasi ogni colloquio sulle liste concatenate.

Verifica rapida

Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

Riepilogo della lezione

In questa lezione ha imparato che: lo schema iterativo Save-Flip-Advance-Advance inverte una lista in O(n) di tempo e O(1) di spazio, l'approccio ricorsivo si basa sul fatto che il suffisso sia già invertito e corregge soltanto l'ultimo collegamento e l'inversione è un passaggio fondamentale nel rilevamento dei palindromi, nel riordinamento della lista e nell'inversione in gruppi di k. Ora analizzeremo il rilevamento dei cicli con l'algoritmo di Floyd.

Domande Frequenti

La lezione «Invertire una linked list» è gratuita?

Sì — il testo completo di «Invertire una linked list» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.

Cosa imparerò in «Invertire una linked list»?

Inverta iterativamente una lista concatenata semplice riconfigurando tre puntatori e lo faccia ricorsivamente, tracciando ogni passaggio su un diagramma in stile lavagna Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Coding Interview Prep?

Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.

Quanto tempo richiede la lezione «Invertire una linked list»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?

Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Classe Node e costruzione delle liste
  2. Invertire una linked list
  3. Rilevamento dei cicli con l'algoritmo di Floyd
  4. Unire, dividere e trovare l'ennesimo elemento dalla fine
← Torna a Coding Interview Prep