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.
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
