LeetCode: Remove Nth Node From End Of List Solution

Approach

Two pointers here is to maintain the position

Target el is

dist from tail

and start from head

First,

will iterate time

• so
  fast
  is
  n
  dist from head (which is also
  slow
  )
• aka,
  slow
  is
  n
  dist from
  fast

Then,

and will both iterate until reach tail

• because target el is
  n
  dist from tail
• and
  slow
  is
  n
  dist from
  fast
  , so the same

Now

is pointed to target, remove that

Implementation

1// no fair-play
2var removeNthFromEnd = function (head, n) {
3  let iter = head
4  let arr = []
5  while (iter) {
6    arr.push(iter.val)
7    iter = iter.next
8  }
9  n = arr.length - n
10  arr.splice(n, 1)
11  arr = arr.map(el => new ListNode(el))
12  for (let i = 0; i < arr.length - 1; i++) {
13    arr[i].next = arr[i + 1]
14  }
15  return arr[0] || null
16}
17
18var removeNthFromEnd = function (head, n) {
19  let fast = (slow = head)
20  while (n--) {
21    fast = fast.next
22  }
23  if (!fast) {
24    return head.next
25  }
26  while (fast.next) {
27    fast = fast.next
28    slow = slow.next
29  }
30  slow.next = slow.next.next
31  return head
32}

References

Original problem

Similar problems

Swapping Nodes in a Linked List

Delete N Nodes After M Nodes of a Linked List

Delete the Middle Node of a Linked List