Inversione In-Place di una Linked List

Una linked list è una struttura dati fondamentale in cui gli elementi (nodi) sono collegati tra loro tramite puntatori. Invertire una linked list è un’operazione comune e farlo in-place significa invertire i collegamenti senza utilizzare memoria aggiuntiva (cioè, senza strutture dati ausiliarie).

In questo articolo esploreremo la tecnica di inversione in-place con esempi in JavaScript.

Perché Invertire una Linked List?

Invertire una linked list è una tecnica cruciale in vari problemi, come ad esempio:

• Invertire sottoelenchi all’interno di una linked list (es. invertire i nodi in gruppi di k)
• Verificare se una linked list è palindroma
• Riorganizzare le linked list per ordinamenti specifici
• Implementare operazioni di stack efficienti

Approccio e Algoritmo per l’Inversione In-Place

L’idea chiave dell’inversione in-place è quella di modificare i puntatori next dei nodi in modo che puntino all’indietro anziché in avanti. Questo viene fatto mantenendo tre puntatori:

1. Precedente (prev): Tiene traccia del nodo precedente a quello corrente.
2. Corrente (curr): Tiene traccia del nodo attualmente in elaborazione.
3. Successivo (nextTemp): Memorizza il nodo successivo per non perdere il riferimento.

Passaggi per Invertire una Linked List In-Place:

1. Inizializza prev come null e curr come la testa della lista.

2. Itera sulla lista finché curr non è null:

   • Salva curr.next in nextTemp.
   • Inverti il collegamento: assegna curr.next = prev.

3. Sposta prev a curr e curr a nextTemp.

Quando curr diventa null, prev sarà la nuova testa della lista invertita.

Implementazione in JavaScript

Di seguito è riportata un’implementazione dell’inversione in-place di una linked list semplicemente collegata:

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function reverseLinkedList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    let nextTemp = curr.next; // Store next node
    curr.next = prev; // Reverse the link
    prev = curr; // Move prev forward
    curr = nextTemp; // Move curr forward
  }

  return prev; // New head
}

// Example usage:
function printList(head) {
  let curr = head;
  let output = [];
  while (curr) {
    output.push(curr.value);
    curr = curr.next;
  }
  console.log(output.join(" -> "));
}

// Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

console.log("Original List:");
printList(head);

head = reverseLinkedList(head);

console.log("Reversed List:");
printList(head);

Complessità Temporale e Spaziale

Complessità Temporale: (Ogni nodo viene visitato una volta)

Complessità Spaziale: (Non viene utilizzata memoria extra oltre a pochi puntatori)

Varianti dell’Inversione In-Place

Invertire un sottoelenco (dalla posizione m alla n)

In alcuni casi, potrebbe essere necessario invertire solo una parte della linked list anziché l’intera lista.

function reverseBetween(head, m, n) {
  if (!head) return null;
  let dummy = new ListNode(0);
  dummy.next = head;
  let prev = dummy;

  for (let i = 0; i < m - 1; i++) {
    prev = prev.next;
  }

  let curr = prev.next;
  let next = null;
  for (let i = 0; i < n - m; i++) {
    next = curr.next;
    curr.next = next.next;
    next.next = prev.next;
    prev.next = next;
  }

  return dummy.next;
}

// Example usage
// head: 5 -> 4 -> 3 -> 2 -> 1
console.log("Reversing sublist from position 2 to 4:");
printList(reverseBetween(head, 2, 4)); // 5 -> 2 -> 3 -> 4 -> 1

Invertire la linked list in segmenti di gruppi di k elementi

Invece di invertire l’intera lista, a volte è necessario invertirla in gruppi di k elementi.

function reverseKGroup(head, k) {
  let count = 0;
  let curr = head;
  while (curr && count < k) {
    curr = curr.next;
    count++;
  }

  if (count === k) {
    curr = reverseKGroup(curr, k);
    while (count-- > 0) {
      let temp = head.next;
      head.next = curr;
      curr = head;
      head = temp;
    }
    head = curr;
  }
  return head;
}

// Example usage
// head: 5 -> 2 -> 3 -> 4 -> 1
console.log("Reversing list in k-group segments (k=3):");
printList(reverseKGroup(head, 3)); // 3 -> 2 -> 5 -> 4 -> 1