Rješavanje problema modifikacije čvorova u povezanim popisima: nemogućnost JavaScripta da postavi čvor na Null

Popravljanje izmjene čvora u JavaScript povezanim popisima: detaljan vodič

Ovo rješenje koristi vanilla JavaScript za izmjenu čvorova na povezanom popisu i pokazuje kako pravilno izbrisati srednji čvor. Također uključuje obradu grešaka i provjeru valjanosti unosa.

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

Alternativni pristup: Promjena vrijednosti čvora umjesto njegovog uklanjanja

Ovaj pristup koristi uobičajeni trik gdje se vrijednost srednjeg čvora zamjenjuje vrijednošću sljedećeg čvora, a zatim se sljedeći čvor uklanja. Time se izbjegava praćenje prethodnog čvora.

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

Uobičajena pitanja o modificiranju čvora povezanog popisa

1. Što znači postavljanje čvora null na povezanom popisu učiniti?
2. Postavljanje čvora na null samo mijenja referencu u toj varijabli, ali ne mijenja izvornu strukturu popisa.
3. Zašto ne b = null izmijeniti popis u primjeru?
4. Kada to učinite b = null, samo mijenja referencu za b, a ne next pokazivač koji povezuje čvorove u povezanoj listi.
5. Kako se briše srednji čvor na povezanoj listi?
6. Vrijednost čvora možete zamijeniti vrijednošću sljedećeg čvora pomoću slow.val = slow.next.val i preskočite sljedeći čvor ažuriranjem next pokazivač.
7. Što je tehnika dvaju pokazivača na povezanom popisu?
8. Uobičajen je pristup gdje se jedan pokazivač (brz) pomiče za dva koraka odjednom, a drugi (spor) za jedan korak kako bi pronašao srednji čvor.
9. Zašto je prev.next = slow.next naredba potrebna za brisanje čvora?
10. Ova naredba ažurira pokazivač prethodnog čvora da preskoči srednji čvor, učinkovito ga brišući s popisa.

Završne misli o brisanju čvorova u povezanim popisima

Rad s povezanim popisima u JavaScriptu često zahtijeva razumijevanje interakcije referenci na objekte i pokazivača. Jednostavno postavljanje čvora na null neće ga ukloniti s popisa; morate ispravno ažurirati pokazivače da biste izbrisali čvorove. Ovo je posebno važno kada se radi o srednjim čvorovima.

Korištenjem tehnike sporog i brzog pokazivača, zajedno s pažljivom manipulacijom pokazivača, možete učinkovito izbrisati čvor s popisa. Ovladavanje ovim tehnikama osigurava da se možete nositi s brisanjem čvorova u povezanim popisima bez neočekivanih rezultata, što je ključna vještina u algoritamskom rješavanju problema.