Remove Nth from end of linked list

In this post, I explore another linked list algorithm. This one is a bit harder.

Create a function to remove the nth node from the end of a linked list.

This comes from a leetcode problem. As in the leetcode problem, ‘n’ is one-based and can go from 1 to the length of the list.

func (ll *LinkedList[T]) RemoveNthFromEnd(n int) *Node[T] { if n == 0 { return nil } fast := ll.Head // this moves to the end slow := ll.Head // this should be one behind the nth from end for count := 0; count < n; count++ { if fast == nil { // list is too short return nil } fast = fast.Next } if fast == nil { // special case, removing head res := ll.Head ll.Head = ll.Head.Next return res } for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next } res := slow.Next slow.Next = slow.Next.Next return res
}

The key to this is using dual pointers. We start by initializing a fast and a slow pointer to the head of the list.

Next, we move the fast pointer n nodes forward. In this way, the slow pointer is now ‘n’ behind the fast pointer. Now, we can move both pointers in lock step until fast is at the end.

We can then remove the nth to last node and return it.

Is there a better way? Let me know in the comments.

Thanks!

The code for this post and all posts in this series can be found here