Solucionar problemes de modificació de nodes a llistes enllaçades: incapacitat de JavaScript per establir un node com a nul

Arreglar la modificació de nodes a les llistes enllaçades de JavaScript: una guia detallada

Aquesta solució utilitza JavaScript de vainilla per modificar els nodes d'una llista enllaçada i demostra com esborrar correctament el node central. També inclou la gestió d'errors i la validació d'entrada.

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function deleteMiddle(head) {
  if (!head || !head.next) return null;  // Handle edge case when list is empty or has only one element
  let slow = head;
  let fast = head;
  let prev = null;

  // Traverse with two pointers (slow and fast)
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }

  // Delete middle node by skipping over it
  prev.next = slow.next;
  return head;
}

// Helper function to print list
function printList(head) {
  let current = head;
  while (current) {
    console.log(current.val);
    current = current.next;
  }
}

// Example usage
let a = new ListNode(1);
let b = new ListNode(2);
let c = new ListNode(3);
let d = new ListNode(4);
let e = new ListNode(5);

a.next = b;
b.next = c;
c.next = d;
d.next = e;

console.log("Before Deletion:");
printList(a);

deleteMiddle(a);

console.log("After Deletion:");
printList(a);

Enfocament alternatiu: modificar el valor del node en lloc d'eliminar-lo

Aquest enfocament aprofita un truc comú en què el valor del node mitjà es substitueix pel valor del node següent i, a continuació, s'elimina el node següent. Això evita haver de fer un seguiment del node anterior.

function deleteMiddleAlternative(head) {
  if (!head || !head.next) return null;  // Handle edge case for single node list
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Replace value of the slow pointer with the next node's value
  if (slow.next) {
    slow.val = slow.next.val;
    slow.next = slow.next.next;
  }
  return head;
}

// Example usage
let x = new ListNode(1);
let y = new ListNode(2);
let z = new ListNode(3);
x.next = y;
y.next = z;

console.log("Before Deletion (Alternative):");
printList(x);

deleteMiddleAlternative(x);

console.log("After Deletion (Alternative):");
printList(x);

Preguntes habituals sobre la modificació del node de la llista enllaçada

1. Què significa configurar un node null en una llista enllaçada fer?
2. Configuració d'un node a null només canvia la referència en aquesta variable, però no altera l'estructura de la llista original.
3. Per què no b = null modificar la llista de l'exemple?
4. Quan ho fas b = null, només canvia la referència per b, no el next punter que connecta els nodes de la llista enllaçada.
5. Com s'elimina un node central d'una llista enllaçada?
6. Podeu substituir el valor del node amb el valor del node següent fent servir slow.val = slow.next.val i saltar el següent node actualitzant el next punter.
7. Quina és la tècnica de dos punters en una llista enllaçada?
8. És un enfocament comú on un punter (ràpid) es mou dos passos alhora i un altre (lent) es mou un pas per trobar el node central.
9. Per què és el prev.next = slow.next ordre necessària per a la supressió de nodes?
10. Aquesta ordre actualitza el punter del node anterior per ometre el node central, eliminant-lo efectivament de la llista.

Pensaments finals sobre la supressió de nodes a les llistes enllaçades

Treballar amb llistes enllaçades a JavaScript sovint requereix entendre com interactuen les referències d'objectes i els punters. Simplement establir un node com a null no l'eliminarà de la llista; heu d'actualitzar correctament els punters per eliminar nodes. Això és especialment important quan es tracta de nodes mitjans.

Mitjançant l'ús de la tècnica del punter lenta i ràpida, juntament amb una manipulació acurada del punter, podeu eliminar de manera eficient un node de la llista. Dominar aquestes tècniques garanteix que podeu gestionar l'eliminació de nodes en llistes enllaçades sense resultats inesperats, que és una habilitat crucial per resoldre problemes algorítmics.