Åtgärda problem med nodändringar i länkade listor: JavaScripts oförmåga att ställa in en nod på noll

Fixa nodändring i länkade JavaScript-listor: En detaljerad guide

Den här lösningen använder vanilla JavaScript för att modifiera noder i en länkad lista och visar hur man korrekt tar bort mittnoden. Det inkluderar även felhantering och indatavalidering.

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);

Alternativ tillvägagångssätt: Ändra nodens värde istället för att ta bort den

Detta tillvägagångssätt utnyttjar ett vanligt knep där värdet på den mellersta noden ersätts med värdet på nästa nod, och sedan tas nästa nod bort. Detta undviker att behöva spåra den föregående noden.

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);

Vanliga frågor om länkad listas nodändring

1. Vad innebär att ställa in en nod null i en länkad lista gör?
2. Ställa in en nod till null ändrar bara referensen i den variabeln, men den ändrar inte den ursprungliga liststrukturen.
3. Varför inte b = null ändra listan i exemplet?
4. När du gör det b = null, det ändrar bara referensen för b, inte next pekare som förbinder noderna i den länkade listan.
5. Hur tar man bort en mittnod i en länkad lista?
6. Du kan antingen ersätta nodens värde med nästa nods värde med hjälp av slow.val = slow.next.val och hoppa över nästa nod genom att uppdatera next pekare.
7. Vad är tvåpekartekniken i en länkad lista?
8. Det är ett vanligt tillvägagångssätt där en pekare (snabbt) flyttar två steg åt gången och en annan (långsamt) flyttar ett steg för att hitta mittnoden.
9. Varför är prev.next = slow.next kommando nödvändigt vid nodborttagning?
10. Detta kommando uppdaterar den föregående nodens pekare så att den hoppar över den mellersta noden, vilket i praktiken tar bort den från listan.

Slutliga tankar om nodborttagning i länkade listor

Att arbeta med länkade listor i JavaScript kräver ofta förståelse för hur objektreferenser och pekare samverkar. Att bara ställa in en nod till null kommer inte att ta bort den från listan; du måste uppdatera pekarna korrekt för att ta bort noder. Detta är särskilt viktigt när man har att göra med mittnoder.

Genom att använda den långsamma och snabba pekartekniken, tillsammans med noggrann pekarmanipulation, kan du effektivt ta bort en nod från listan. Att behärska dessa tekniker säkerställer att du kan hantera nodradering i länkade listor utan oväntade resultat, vilket är en avgörande färdighet i algoritmisk problemlösning.