Khắc phục sự cố sửa đổi nút trong danh sách liên kết: JavaScript không thể đặt nút thành null

Sửa lỗi sửa đổi nút trong danh sách liên kết JavaScript: Hướng dẫn chi tiết

Giải pháp này sử dụng JavaScript nguyên bản để sửa đổi các nút trong Danh sách liên kết và trình bày cách xóa nút giữa đúng cách. Nó cũng bao gồm việc xử lý lỗi và xác nhận đầu vào.

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

Phương pháp thay thế: Sửa đổi giá trị của nút thay vì xóa nó

Cách tiếp cận này tận dụng một thủ thuật phổ biến trong đó giá trị của nút giữa được thay thế bằng giá trị của nút tiếp theo và sau đó nút tiếp theo sẽ bị xóa. Điều này tránh phải theo dõi nút trước đó.

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

Các câu hỏi thường gặp về sửa đổi nút danh sách liên kết

1. Việc thiết lập một nút thành gì null trong danh sách liên kết phải làm gì?
2. Đặt một nút thành null chỉ thay đổi tham chiếu trong biến đó nhưng không làm thay đổi cấu trúc danh sách ban đầu.
3. Tại sao không b = null sửa đổi danh sách trong ví dụ?
4. Khi bạn làm b = null, nó chỉ thay đổi tham chiếu cho b, không phải next con trỏ kết nối các nút trong danh sách liên kết.
5. Làm cách nào để xóa nút giữa trong danh sách liên kết?
6. Bạn có thể thay thế giá trị của nút bằng giá trị của nút tiếp theo bằng cách sử dụng slow.val = slow.next.val và bỏ qua nút tiếp theo bằng cách cập nhật next con trỏ.
7. Kỹ thuật hai con trỏ trong danh sách liên kết là gì?
8. Đó là một cách tiếp cận phổ biến trong đó một con trỏ (nhanh) di chuyển hai bước cùng một lúc và một con trỏ khác (chậm) di chuyển một bước để tìm nút giữa.
9. Tại sao là prev.next = slow.next lệnh cần thiết trong việc xóa nút?
10. Lệnh này cập nhật con trỏ của nút trước đó để bỏ qua nút giữa, xóa nó khỏi danh sách một cách hiệu quả.

Suy nghĩ cuối cùng về việc xóa nút trong danh sách liên kết

Làm việc với danh sách liên kết trong JavaScript thường đòi hỏi phải hiểu cách tương tác giữa các tham chiếu đối tượng và con trỏ. Việc chỉ đặt một nút thành null sẽ không xóa nút đó khỏi danh sách; bạn phải cập nhật con trỏ chính xác để xóa các nút. Điều này đặc biệt quan trọng khi xử lý các nút ở giữa.

Bằng cách sử dụng kỹ thuật con trỏ chậm và nhanh, cùng với thao tác con trỏ cẩn thận, bạn có thể xóa một nút khỏi danh sách một cách hiệu quả. Việc nắm vững các kỹ thuật này đảm bảo bạn có thể xử lý việc xóa nút trong danh sách liên kết mà không gặp phải kết quả không mong muốn, đây là một kỹ năng quan trọng trong việc giải quyết vấn đề bằng thuật toán.