Виправлення проблем модифікації вузлів у пов’язаних списках: неможливість JavaScript встановити вузол у значення Null

Виправлення модифікації вузла в пов’язаних списках JavaScript: докладний посібник

Це рішення використовує ванільний JavaScript для зміни вузлів у зв’язаному списку та демонструє, як правильно видалити середній вузол. Він також включає обробку помилок і перевірку введених даних.

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 не видалить його зі списку; ви повинні правильно оновити покажчики, щоб видалити вузли. Це особливо важливо при роботі з середніми вузлами.

Використовуючи техніку повільного та швидкого вказівника разом із обережним маніпулюванням вказівником, ви можете ефективно видалити вузол зі списку. Оволодіння цими техніками гарантує, що ви зможете впоратися з видаленням вузлів у пов’язаних списках без неочікуваних результатів, що є ключовим навиком у алгоритмічному розв’язанні проблем.