19. Remove Nth Node From End of List

Problem

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  var h = new ListNode(0);
  var ll = h;
  var rr = h;

  h.next = head;

  for (var i = 0; i < n + 1; i++) {
    rr = rr.next;
  }

  while (rr !== null) {
    ll = ll.next;
    rr= rr.next;
  }

  ll.next = ll.next.next;

  return h.next;
};

Explain:

1. 两个指针 a, b，初始都指向开头
2. 把 b 指针往后移动，直到两指针的位置相差 n
3. 同时移动两指针，直到 b 指针到了最后。这时候因为两指针的位置相差 n，a 指针的位置就是从后面数第 n+1 个
4. 在 a 指针那里删掉后面一个，即第 n 个

要注意可能会出现删掉 head 的情况。

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).