Mezglu modifikācijas problēmu novēršana saistītajos sarakstos: JavaScript nespēja iestatīt mezglu uz nulli

Mezglu modifikāciju labošana JavaScript saistītos sarakstos: detalizēta rokasgrāmata

Šis risinājums izmanto vaniļas JavaScript, lai modificētu mezglus saistītajā sarakstā, un parāda, kā pareizi izdzēst vidējo mezglu. Tas ietver arī kļūdu apstrādi un ievades validāciju.

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

Alternatīva pieeja: mezgla vērtības modificēšana, nevis tā noņemšana

Šī pieeja izmanto izplatītu triku, kad vidējā mezgla vērtība tiek aizstāta ar nākamā mezgla vērtību un pēc tam tiek noņemts nākamais mezgls. Tas ļauj izvairīties no nepieciešamības izsekot iepriekšējam mezglam.

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

Bieži uzdotie jautājumi par saistīto sarakstu mezglu modifikāciju

1. Ko nozīmē mezgla iestatīšana null saistītā sarakstā darīt?
2. Notiek mezgla iestatīšana uz null maina tikai atsauci šajā mainīgajā, bet nemaina sākotnējo saraksta struktūru.
3. Kāpēc ne b = null mainīt piemēra sarakstu?
4. Kad jūs to darāt b = null, tas tikai maina atsauci uz b, nevis next rādītājs, kas savieno mezglus saistītajā sarakstā.
5. Kā dzēst vidējo mezglu saistītajā sarakstā?
6. Varat vai nu aizstāt mezgla vērtību ar nākamā mezgla vērtību, izmantojot slow.val = slow.next.val un izlaidiet nākamo mezglu, atjauninot next rādītājs.
7. Kas ir divpunktu metienu tehnika saistītajā sarakstā?
8. Tā ir izplatīta pieeja, kad viens rādītājs (ātri) pārvieto divus soļus vienlaikus, bet otrs (lēni) pārvietojas vienu soli, lai atrastu vidējo mezglu.
9. Kāpēc ir prev.next = slow.next komanda ir nepieciešama mezgla dzēšanai?
10. Šī komanda atjaunina iepriekšējā mezgla rādītāju, lai izlaistu virs vidējā mezgla, efektīvi izdzēšot to no saraksta.

Pēdējās domas par mezglu dzēšanu saistītajos sarakstos

Lai strādātu ar saistītajiem sarakstiem JavaScript, bieži ir jāsaprot, kā mijiedarbojas objektu atsauces un norādes. Vienkārši iestatot mezglu uz nulli, tas netiks noņemts no saraksta; lai dzēstu mezglus, norādes ir pareizi jāatjaunina. Tas ir īpaši svarīgi, strādājot ar vidējiem mezgliem.

Izmantojot lēnās un ātrās rādītāja paņēmienu, kā arī rūpīgi manipulējot ar rādītāju, varat efektīvi izdzēst mezglu no saraksta. Šo metožu apgūšana nodrošina, ka varat dzēst mezglu saistītos sarakstos bez negaidītiem rezultātiem, kas ir ļoti svarīga algoritmiskā problēmu risināšanas prasme.