Lingitud loendite sõlmede muutmise probleemide parandamine: JavaScripti suutmatus sõlme nulliks seada

Sõlme muutmise parandamine JavaScripti lingitud loendites: üksikasjalik juhend

See lahendus kasutab lingitud loendi sõlmede muutmiseks vanilje JavaScripti ja näitab, kuidas keskmist sõlme õigesti kustutada. See hõlmab ka vigade käsitlemist ja sisendi valideerimist.

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

Alternatiivne lähenemisviis: sõlme väärtuse muutmine selle eemaldamise asemel

See lähenemisviis kasutab levinud nippi, kus keskmise sõlme väärtus asendatakse järgmise sõlme väärtusega ja seejärel eemaldatakse järgmine sõlm. See väldib eelmise sõlme jälgimist.

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

Levinud küsimused lingitud loendi sõlmede muutmise kohta

1. Mida tähendab sõlme seadistamine null lingitud loendis teha?
2. Sõlme määramine null muudab ainult selle muutuja viidet, kuid see ei muuda loendi algset struktuuri.
3. Miks mitte b = null muuta näites olevat loendit?
4. Kui teete b = null, muudab see lihtsalt viidet b, mitte next osuti, mis ühendab lingitud loendis olevaid sõlmi.
5. Kuidas lingitud loendist keskmist sõlme kustutada?
6. Saate sõlme väärtuse asendada järgmise sõlme väärtusega, kasutades slow.val = slow.next.val ja jätke vahele järgmine sõlm, värskendades next osuti.
7. Mis on kahepunktitehnika lingitud loendis?
8. See on levinud lähenemisviis, kus üks osuti (kiire) liigub kaks sammu korraga ja teine ​​(aeglane) liigub ühe sammu keskmise sõlme leidmiseks.
9. Miks on prev.next = slow.next sõlme kustutamisel vajalik käsk?
10. See käsk värskendab eelmise sõlme kursorit keskmise sõlme vahelejätmiseks, kustutades selle loendist tõhusalt.

Viimased mõtted sõlmede kustutamise kohta lingitud loendites

JavaScriptis lingitud loenditega töötamine nõuab sageli arusaamist, kuidas objektiviited ja viited omavahel suhtlevad. Kui määrate sõlme lihtsalt nulliks, ei eemaldata seda loendist. sõlmede kustutamiseks peate viiteid õigesti värskendama. See on eriti oluline keskmiste sõlmedega tegelemisel.

Aeglase ja kiire kursori tehnikat kasutades koos hoolika kursoriga manipuleerimisega saate sõlme loendist tõhusalt kustutada. Nende tehnikate valdamine tagab, et saate lingitud loendites sõlmede kustutamisega hakkama ilma ootamatute tulemusteta, mis on algoritmilise probleemide lahendamise ülioluline oskus.