remove nth node from end

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class List {
  constructor() {
    this.head = null;
  }
}

List.prototype.add = function (val) {
  let curr = this.head;
  const newNode = new Node(val);

  if (!curr) {
    this.head = newNode; // this.head
  } else {
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = newNode;
  }
};

List.prototype.createList = function (arr) {
  const dummy = new ListNode(null);
  let curr = dummy;

  while (arr.length) {
    curr.next = new ListNode(arr.shift());
    curr = curr.next;
  }
  return dummy.next;
};

const list = new List();
const linkedList = list.createList([1, 2]);

// var removeNthFromEnd = function (head, n) {
//   if (!head) return null;

//   let dummy = new ListNode(null);
//   dummy.next = head;
//   let curr = head;
//   let size = 0;

//   // find total size;
//   while (curr) {
//     size++;
//     curr = curr.next;
//   }

//   // reset curr to dummy
//   curr = dummy;

//   // move curr to before target
//   for (let i = 0; i < size - n; i++) {
//     curr = curr.next;
//   }

//   // remove target
//   curr.next = curr.next.next;
//   return dummy.next;
// };

// two pointer
var removeNthFromEnd = function (head, n) {
  if (!head) return null;

  let dummy = new ListNode(null);
  dummy.next = head;

  let fastP = dummy;
  let slowP = dummy;

  // move fastP
  for (let i = 0; i < n + 1; i++) {
    fastP = fastP.next;
  }

  // move fastP, slowP until fastP reach the end.
  // slowP reached (end - n - 1) means the next node is the target node
  while (fastP) {
    fastP = fastP.next;
    slowP = slowP.next;
  }

  // remove target node
  slowP.next = slowP.next.next;
  return dummy.next;
};

console.log(removeNthFromEnd(linkedList, 2)); // 1235