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

The above is the detailed content of Remove Nth from end of linked list. For more information, please follow other related articles on the PHP Chinese website!