Odpravljanje težav s spreminjanjem vozlišč v povezanih seznamih: JavaScript nezmožnost nastaviti vozlišče na nič

Popravljanje sprememb vozlišča v povezanih seznamih JavaScript: Podroben vodnik

Ta rešitev uporablja neobičajni JavaScript za spreminjanje vozlišč na povezanem seznamu in prikazuje, kako pravilno izbrisati srednje vozlišče. Vključuje tudi obravnavanje napak in preverjanje vnosa.

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 pristop: Spreminjanje vrednosti vozlišča, namesto da bi ga odstranili

Ta pristop uporablja običajen trik, pri katerem se vrednost srednjega vozlišča nadomesti z vrednostjo naslednjega vozlišča, nato pa se naslednje vozlišče odstrani. S tem se izognete sledenju prejšnjemu vozlišču.

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

Pogosta vprašanja o spreminjanju vozlišča povezanega seznama

1. Kaj pomeni nastavitev vozlišča null na povezanem seznamu narediti?
2. Nastavitev vozlišča na null spremeni le sklic v tej spremenljivki, vendar ne spremeni prvotne strukture seznama.
3. Zakaj pa ne b = null spremenite seznam v primeru?
4. Ko to storite b = null, samo spremeni sklic za b, ne pa next kazalec, ki povezuje vozlišča na povezanem seznamu.
5. Kako izbrišete srednje vozlišče na povezanem seznamu?
6. Vrednost vozlišča lahko zamenjate z vrednostjo naslednjega vozlišča z uporabo slow.val = slow.next.val in preskočite naslednje vozlišče tako, da posodobite next kazalec.
7. Kaj je tehnika dveh kazalcev na povezanem seznamu?
8. To je običajen pristop, pri katerem se en kazalec (hiter) premakne za dva koraka naenkrat, drugi (počasen) pa za en korak, da najde srednje vozlišče.
9. Zakaj je prev.next = slow.next ukaz potreben pri brisanju vozlišča?
10. Ta ukaz posodobi kazalec prejšnjega vozlišča, da preskoči srednje vozlišče in ga dejansko izbriše s seznama.

Končne misli o brisanju vozlišč na povezanih seznamih

Delo s povezanimi seznami v JavaScriptu pogosto zahteva razumevanje interakcije referenc objektov in kazalcev. Preprosta nastavitev vozlišča na ničelno vrednost ga ne bo odstranila s seznama; morate pravilno posodobiti kazalce, da izbrišete vozlišča. To je še posebej pomembno pri obravnavanju srednjih vozlišč.

Z uporabo tehnike počasnega in hitrega kazalca, skupaj s skrbnim ravnanjem s kazalcem, lahko učinkovito izbrišete vozlišče s seznama. Obvladovanje teh tehnik zagotavlja, da lahko upravljate z brisanjem vozlišč na povezanih seznamih brez nepričakovanih rezultatov, kar je ključna veščina pri algoritemskem reševanju težav.