Mazgo keitimo problemų sprendimas susietuose sąrašuose: „JavaScript“ nesugebėjimas nustatyti mazgo į nulį

Mazgo modifikacijos taisymas „JavaScript“ susietuose sąrašuose: išsamus vadovas

Šis sprendimas naudoja vanilinį JavaScript, kad modifikuotų susietojo sąrašo mazgus ir parodytų, kaip tinkamai ištrinti vidurinį mazgą. Tai taip pat apima klaidų tvarkymą ir įvesties patvirtinimą.

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

Alternatyvus būdas: pakeisti mazgo vertę, o ne jį pašalinti

Šis metodas naudoja įprastą triuką, kai vidurinio mazgo reikšmė pakeičiama kito mazgo reikšme, o tada kitas mazgas pašalinamas. Taip išvengiama ankstesnio mazgo sekimo.

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

Dažni klausimai apie susieto sąrašo mazgų modifikavimą

1. Ką reiškia mazgo nustatymas null susietame sąraše daryti?
2. Mazgo nustatymas į null pakeičia tik nuorodą tame kintamajame, bet nekeičia pradinės sąrašo struktūros.
3. Kodėl ne b = null pakeisti pavyzdyje pateiktą sąrašą?
4. Kai tai padarysi b = null, tai tik pakeičia nuorodą b, o ne next žymeklį, jungiantį susieto sąrašo mazgus.
5. Kaip ištrinti vidurinį mazgą susietame sąraše?
6. Galite arba pakeisti mazgo vertę kito mazgo reikšme naudodami slow.val = slow.next.val ir praleiskite kitą mazgą atnaujindami next rodyklė.
7. Kas yra dvitaškio technika susietame sąraše?
8. Tai įprastas metodas, kai vienas žymeklis (greitas) vienu metu perkelia du žingsnius, o kitas (lėtas) perkelia vieną žingsnį, kad surastų vidurinį mazgą.
9. Kodėl yra prev.next = slow.next komanda reikalinga ištrinant mazgą?
10. Ši komanda atnaujina ankstesnio mazgo žymeklį, kad būtų praleistas vidurinis mazgas, veiksmingai pašalinant jį iš sąrašo.

Paskutinės mintys apie mazgų ištrynimą susietuose sąrašuose

Norint dirbti su susietais sąrašais „JavaScript“, dažnai reikia suprasti, kaip sąveikauja objektų nuorodos ir rodyklės. Paprasčiausiai nustačius mazgą į nulį, jis nebus pašalintas iš sąrašo; turite teisingai atnaujinti rodykles, kad ištrintumėte mazgus. Tai ypač svarbu dirbant su viduriniais mazgais.

Naudodami lėtą ir greitą žymeklio techniką bei atidžiai manipuliuodami žymekliu, galite efektyviai ištrinti mazgą iš sąrašo. Įvaldę šiuos metodus, galite pašalinti mazgus susietuose sąrašuose be netikėtų rezultatų, o tai yra esminis algoritminio problemų sprendimo įgūdis.