Διόρθωση προβλημάτων τροποποίησης κόμβου σε συνδεδεμένες λίστες: Αδυναμία της JavaScript να ορίσει έναν κόμβο σε Null

Διόρθωση τροποποίησης κόμβου σε λίστες συνδεδεμένων με JavaScript: Λεπτομερής οδηγός

Αυτή η λύση χρησιμοποιεί JavaScript vanilla για την τροποποίηση κόμβων σε μια Συνδεδεμένη λίστα και δείχνει πώς να διαγράψετε σωστά τον μεσαίο κόμβο. Περιλαμβάνει επίσης χειρισμό σφαλμάτων και επικύρωση εισόδου.

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

Εναλλακτική προσέγγιση: Τροποποίηση της τιμής του κόμβου αντί της κατάργησής του

Αυτή η προσέγγιση αξιοποιεί ένα κοινό κόλπο όπου η τιμή του μεσαίου κόμβου αντικαθίσταται με την τιμή του επόμενου κόμβου και, στη συνέχεια, αφαιρείται ο επόμενος κόμβος. Αυτό αποφεύγει την ανάγκη παρακολούθησης του προηγούμενου κόμβου.

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

Συνήθεις ερωτήσεις σχετικά με την τροποποίηση κόμβου συνδεδεμένης λίστας

1. Τι σημαίνει η ρύθμιση ενός κόμβου null σε μια συνδεδεμένη λίστα κάνω;
2. Ρύθμιση κόμβου σε null αλλάζει μόνο την αναφορά σε αυτήν τη μεταβλητή, αλλά δεν αλλάζει την αρχική δομή της λίστας.
3. Γιατί όχι b = null να τροποποιήσετε τη λίστα στο παράδειγμα;
4. Όταν το κάνετε b = null, αλλάζει απλώς την αναφορά για b, όχι το next δείκτη που συνδέει τους κόμβους στη συνδεδεμένη λίστα.
5. Πώς διαγράφετε έναν μεσαίο κόμβο σε μια συνδεδεμένη λίστα;
6. Μπορείτε είτε να αντικαταστήσετε την τιμή του κόμβου με την τιμή του επόμενου κόμβου χρησιμοποιώντας slow.val = slow.next.val και παρακάμψτε τον επόμενο κόμβο ενημερώνοντας το next δείκτης.
7. Ποια είναι η τεχνική των δύο πόντων σε μια συνδεδεμένη λίστα;
8. Είναι μια κοινή προσέγγιση όπου ένας δείκτης (γρήγορα) κινείται δύο βήματα τη φορά και ένας άλλος (αργά) κινείται ένα βήμα για να βρει τον μεσαίο κόμβο.
9. Γιατί είναι το prev.next = slow.next εντολή που απαιτείται για τη διαγραφή κόμβου;
10. Αυτή η εντολή ενημερώνει τον δείκτη του προηγούμενου κόμβου για να παρακάμψει τον μεσαίο κόμβο, διαγράφοντάς τον ουσιαστικά από τη λίστα.

Τελικές σκέψεις σχετικά με τη διαγραφή κόμβων σε συνδεδεμένες λίστες

Η εργασία με συνδεδεμένες λίστες σε JavaScript απαιτεί συχνά την κατανόηση του τρόπου με τον οποίο αλληλεπιδρούν οι αναφορές αντικειμένων και οι δείκτες. Η απλή ρύθμιση ενός κόμβου σε null δεν θα τον αφαιρέσει από τη λίστα. πρέπει να ενημερώσετε σωστά τους δείκτες για να διαγράψετε κόμβους. Αυτό είναι ιδιαίτερα σημαντικό όταν έχουμε να κάνουμε με μεσαίους κόμβους.

Χρησιμοποιώντας την τεχνική αργού και γρήγορου δείκτη, μαζί με προσεκτικό χειρισμό δείκτη, μπορείτε να διαγράψετε αποτελεσματικά έναν κόμβο από τη λίστα. Η γνώση αυτών των τεχνικών διασφαλίζει ότι μπορείτε να χειριστείτε τη διαγραφή κόμβων σε συνδεδεμένες λίστες χωρίς απροσδόκητα αποτελέσματα, κάτι που είναι μια κρίσιμη δεξιότητα στην αλγοριθμική επίλυση προβλημάτων.