LeetCode: Remove Nth Node From End Of List Solution

Approach

Two pointers here is to maintain the position

Target el is

n
dist from tail

fast
and
slow

First,

fast
will iterate
n
time

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

Then,

fast
and
slow
will both iterate until
fast
reach tail

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

Now

slow
is pointed to target, remove that

Implementation

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}// no fair-play2var removeNthFromEnd = function (head, n) {3  let iter = head4  let arr = []5  while (iter) {6    arr.push(iter.val)7    iter = iter.next8  }9  n = arr.length - n10  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] || null16}17
18var removeNthFromEnd = function (head, n) {19  let fast = (slow = head)20  while (n--) {21    fast = fast.next22  }23  if (!fast) {24    return head.next25  }26  while (fast.next) {27    fast = fast.next28    slow = slow.next29  }30  slow.next = slow.next.next31  return head32}```

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

leetcode

two pointers

Next Post

LeetCode: N Ary Tree Preorder Traversal

Apr 21, 2021

Search Posts