Csomópontmódosítási problémák javítása a linkelt listákban: a JavaScript nem képes nullára állítani a csomópontot

Csomópont-módosítás javítása JavaScript-hivatkozási listákban: Részletes útmutató

Ez a megoldás vanília JavaScriptet használ a linkelt lista csomópontjainak módosítására, és bemutatja, hogyan kell megfelelően törölni a középső csomópontot. Ez magában foglalja a hibakezelést és a bemenet érvényesítését is.

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ív megközelítés: a csomópont értékének módosítása eltávolítása helyett

Ez a megközelítés egy általános trükköt alkalmaz, ahol a középső csomópont értékét lecserélik a következő csomópont értékére, majd a következő csomópontot eltávolítják. Ezzel elkerülhető az előző csomópont nyomon követése.

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

Gyakori kérdések a linkelt lista csomópontjának módosításával kapcsolatban

1. Mit jelent a csomópont beállítása null egy linkelt listában csinálni?
2. Csomópont beállítása a null csak a hivatkozást változtatja meg az adott változóban, de nem változtatja meg az eredeti listaszerkezetet.
3. Miért nem b = null módosítja a példában szereplő listát?
4. Amikor megteszed b = null, csak megváltoztatja a hivatkozást b, nem a next mutató, amely összeköti a hivatkozott lista csomópontjait.
5. Hogyan lehet törölni egy középső csomópontot egy linkelt listából?
6. A csomópont értékét lecserélheti a következő csomópont értékére slow.val = slow.next.val és ugorja át a következő csomópontot a next mutató.
7. Mi a kétmutatós technika egy linkelt listában?
8. Ez egy elterjedt megközelítés, amikor az egyik mutató (gyorsan) egyszerre két lépést, egy másik (lassú) pedig egy lépést mozgat, hogy megtalálja a középső csomópontot.
9. Miért van az prev.next = slow.next parancs szükséges a csomópont törléséhez?
10. Ez a parancs frissíti az előző csomópont mutatóját, hogy átugorja a középső csomópontot, és gyakorlatilag törli azt a listáról.

Utolsó gondolatok a csomópontok törlésével kapcsolatban a linkelt listákban

A hivatkozott listák JavaScriptben való használata gyakran megköveteli az objektumhivatkozások és mutatók kölcsönhatásának megértését. Egy csomópont nullára állítása nem távolítja el a listáról; helyesen kell frissítenie a mutatókat a csomópontok törléséhez. Ez különösen fontos a középső csomópontok kezelésekor.

A lassú és gyors mutató technika használatával, valamint a mutató gondos manipulálásával hatékonyan törölhet egy csomópontot a listáról. E technikák elsajátítása biztosítja, hogy váratlan eredmények nélkül kezelje a csomópontok törlését a csatolt listákban, ami kulcsfontosságú készség az algoritmikus problémamegoldásban.