Removing nth Node From End of Linked List

The most basic approach to this problem would be to iterate over the entire linked list once to find out the length of the list. Then iterate over it again to locate the node to be removed. This can be done in the following way:

Let n be the length of the list and we need to remove the mth element from the end so we will have to remove the (n-m)th element from the list.

However this approach requires having to iterate over the list twice and hence the time complexity will be O(2n). We can solve this problem in O(n) time complexity also by using the following approach:

• Declare 2 pointers – last and prev and initialize both of them to to point to head
• Iterate the last pointer m times.
• Iterate both the pointers last and prev till last.next == null.

After following these 3 steps out prev pointer will be pointing to the node just before the one that needs to be removed from the list. Now we can simply remove the required node by pointing prev.next to prev.next.next

static void remove_nth_node(LinkedList l, int n) 
{
        Node last = l.head;
        Node prev = l.head;
        for (int i = 0; i < n; i++)
        {
            last = last.next;
        }
        while (last.next != null)
        {
            last = last.next;
            prev = prev.next;
        }
        prev.next = prev.next.next;
}