19. Remove Nth Node From End of List

原题：19. Remove Nth Node From End of List

这道题考察的是滑动窗口。

解法一

时间复杂度：O(n)

// Runtime: 76 ms, faster than 14.67% of JavaScript online submissions for Remove Nth Node From End of List.
// Memory Usage: 34.8 MB, less than 13.64% of JavaScript online submissions for Remove Nth Node From End of List.
var removeNthFromEnd = function (head, n) {
  const queue = [];
  const enqueue = function (node) {
    if (queue.length >= n + 1) {
      queue.shift();
    }
    queue.push(node);
  };

  const _head = new ListNode();
  _head.next = head;
  let cur = _head;
  while (cur) {
    enqueue(cur);
    cur = cur.next;
  }

  queue[0].next = queue[2] || null; //删除
  queue[1].next = null; //清理

  return _head.next;
};

解法二（Recommend）

时间复杂度：O(n)

比解法一优化了空间复杂度，只保留了窗口的头尾指针。

// Runtime: 96 ms, faster than 8.34% of JavaScript online submissions for Remove Nth Node From End of List.
// Memory Usage: 34.1 MB, less than 68.18% of JavaScript online submissions for Remove Nth Node From End of List.
var removeNthFromEnd = function (head, n) {
  const _head = new ListNode();
  _head.next = head;
  let left = _head;
  let right = _head;

  while (n-- >= 0) {
    right = right.next;
  }
  while (right) {
    left = left.next;
    right = right.next;
  }
  left.next = left.next.next;

  return _head.next;
};

Test Cases:

test("test1", () => {
  expect(removeNthFromEnd(makeLink([1, 2, 3, 4, 5]), 2)).toEqual(
    makeLink([1, 2, 3, 5])
  );
});

test("test2", () => {
  expect(removeNthFromEnd(makeLink([1]), 1)).toEqual(makeLink([]));
});