Double Linked Lists - Esercizi

1
isPalindrome() {
2
  // Edge case: lista vuota o con un solo nodo è sempre palindromo
3
  if (this.length <= 1) return true;
4

5
  // Puntatore che parte da head (inizio)
6
  let forward = this.head;
7
  // Puntatore che parte da tail (fine)
8
  let backward = this.tail;
9

10
  // Itera per metà della lunghezza (floor per gestire numeri dispari)
11
  for (let i = 0; i < Math.floor(this.length / 2); i++) {
12
    // Se i valori corrispondono e i puntatori non si sono incontrati
13
    if (forward.value === backward.value && forward !== backward) {
14
      // Avanza forward in avanti
15
      forward = forward.next;
16
      // Avanza backward all'indietro
17
      backward = backward.prev;
18
    } else {
19
      // Se i valori non corrispondono, non è un palindromo
20
      return false;
21
    }
22
  }
23

24
  // Tutti i valori corrispondono, è un palindromo
25
  return true;
26
}

1
reverse() {
2
  // Puntatore che parte da head
3
  let current = this.head;
4
  // Variabile temporanea per salvare i riferimenti durante lo scambio
5
  let temp = null;
6

7
  // Itera attraverso tutta la lista
8
  while (current !== null) {
9
    // Salva il puntatore prev prima di modificarlo
10
    temp = current.prev;
11
    // Scambia: prev diventa next
12
    current.prev = current.next;
13
    // Scambia: next diventa prev (salvato in temp)
14
    current.next = temp;
15
    // Avanza al prossimo nodo usando prev (che ora punta dove prima c'era next)
16
    current = current.prev;
17
  }
18

19
  // Scambia head e tail
20
  temp = this.head;
21
  this.head = this.tail;
22
  this.tail = temp;
23
}

1
partitionList(x) {
2
  // Edge case: lista vuota
3
  if (!this.head) return;
4

5
  // Crea due dummy nodes per le due partizioni
6
  const dummy1 = new Node(0);  // Per valori < x
7
  const dummy2 = new Node(0);  // Per valori >= x
8

9
  // Puntatori per costruire le due liste
10
  let prev1 = dummy1;
11
  let prev2 = dummy2;
12

13
  // Puntatore per iterare attraverso la lista originale
14
  let current = this.head;
15

16
  // Distribuisci i nodi nelle due liste
17
  while (current !== null) {
18
    // Salva il prossimo nodo prima di staccare current
19
    const nextNode = current.next;
20

21
    // Stacca current dalla lista originale
22
    current.next = null;
23
    current.prev = null;
24

25
    // Se il valore è minore di x, aggiungi alla prima lista
26
    if (current.value < x) {
27
      prev1.next = current;
28
      current.prev = prev1;
29
      prev1 = current;
30
    } else {
31
      // Altrimenti, aggiungi alla seconda lista
32
      prev2.next = current;
33
      current.prev = prev2;
34
      prev2 = current;
35
    }
36

37
    // Passa al prossimo nodo
38
    current = nextNode;
39
  }
40

41
  // Termina la seconda lista
42
  prev2.next = null;
43

44
  // Collega le due liste
45
  prev1.next = dummy2.next;
46
  // Edge case importante: verifica che la seconda lista non sia vuota
47
  if (dummy2.next) {
48
    dummy2.next.prev = prev1;
49
  }
50

51
  // Aggiorna head alla nuova testa
52
  this.head = dummy1.next;
53

54
  // Assicura che head non abbia un puntatore prev
55
  if (this.head) {
56
    this.head.prev = null;
57
  }
58
}

1
reverseBetween(startIndex, endIndex) {
2
  // Edge case: lista vuota o range non valido
3
  if (!this.head || startIndex === endIndex) return;
4

5
  // Crea un dummy node per semplificare le operazioni
6
  const dummy = new Node(0);
7
  dummy.next = this.head;
8
  this.head.prev = dummy;
9

10
  // Trova il nodo prima del range da invertire
11
  let prev = dummy;
12
  for (let i = 0; i < startIndex; i++) {
13
    prev = prev.next;
14
  }
15

16
  // Inizio del sottolista da invertire
17
  let current = prev.next;
18

19
  // Inverti i nodi spostandoli uno alla volta all'inizio del range
20
  for (let i = 0; i < endIndex - startIndex; i++) {
21
    // Nodo da spostare
22
    const nodeToMove = current.next;
23

24
    // Rimuovi nodeToMove dalla sua posizione corrente
25
    current.next = nodeToMove.next;
26
    if (nodeToMove.next) {
27
      nodeToMove.next.prev = current;
28
    }
29

30
    // Inserisci nodeToMove dopo prev
31
    nodeToMove.next = prev.next;
32
    prev.next.prev = nodeToMove;
33

34
    prev.next = nodeToMove;
35
    nodeToMove.prev = prev;
36
  }
37

38
  // Ripristina head al primo nodo dopo dummy
39
  this.head = dummy.next;
40
  this.head.prev = null;
41
}

1
swapPairs() {
2
  // Crea un dummy node per semplificare la gestione del primo swap
3
  const dummy = new Node(0);
4
  dummy.next = this.head;
5

6
  // Puntatore al nodo precedente alla coppia corrente
7
  let prev = dummy;
8

9
  // Scambia coppie finché ci sono almeno due nodi
10
  while (this.head !== null && this.head.next !== null) {
11
    // Primo nodo della coppia
12
    const firstNode = this.head;
13
    // Secondo nodo della coppia
14
    const secondNode = this.head.next;
15

16
    // Collega prev al secondo nodo (che diventerà il primo)
17
    prev.next = secondNode;
18
    // Il primo nodo punta a ciò che era dopo il secondo
19
    firstNode.next = secondNode.next;
20
    // Il secondo nodo punta al primo (scambio)
21
    secondNode.next = firstNode;
22

23
    // Gestione puntatori prev
24
    secondNode.prev = prev;
25
    firstNode.prev = secondNode;
26
    // Se c'è un nodo dopo firstNode, aggiorna il suo prev
27
    if (firstNode.next !== null) {
28
      firstNode.next.prev = firstNode;
29
    }
30

31
    // Avanza head alla prossima coppia
32
    this.head = firstNode.next;
33
    // Aggiorna prev per la prossima iterazione
34
    prev = firstNode;
35
  }
36

37
  // Aggiorna head al primo nodo dopo dummy
38
  this.head = dummy.next;
39
  // Assicura che head non abbia un puntatore prev
40
  if (this.head) {
41
    this.head.prev = null;
42
  }
43
}