Tìm nút giữa của danh sách liên kết trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào nút đầu (head) của một danh sách liên kết làm đối số duy nhất. Hàm phải trả về giá trị lưu trong nút giữa của danh sách. Nếu có hai nút giữa, trả về nút thứ hai.

Ví dụ, nếu danh sách như sau:

Đầu vào

[4, 6, 8, 9, 1]

Đầu ra

const output = 8;

Ví dụ

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
}
LinkedList.prototype.add = function(data) {
  const newNode = new Node(data);
  let curr;
  if (this.head === null) {
    this.head = newNode;
  } else {
    curr = this.head;
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = newNode;
  }
  this.size++;
};
const list = new LinkedList();
list.add(4);
list.add(6);
list.add(8);
list.add(9);
list.add(1);
const findMiddle = (head) => {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow.data;
};
console.log(findMiddle(list.head));

Kết quả

8