Given a pointer to the head of a singly linked list and a number n, delete the node at nth position in the linked list.

You need to write a method with signature Node* Delete(Node *head, int n) where head is pointer to the head of the linked list and n is the position of the node from beginning (on 0-based index) to be deleted.

Your method must return pointer to the head node of the modified linked list.

We will see how to delete the nth node from a linked list.

To delete an element, we need to do two operations.

• Modify the next value of (n-1)th element.
• Delete (Free up memory) of the nth element.

We traverse the linked list, until we are in the nth position using two node pointers. One which points to the ith element in each step, and another to point to it's previous. We apply the operation and return the head.

A special case to consider is deleting the first element. The head is changed, and there is no previous element. We check that separtely and we are done.

Time Complexity: O(n) for the traversal.

Space Complexity: O(1)

editorial written by ash1794

Node* Delete(Node *head, int n)
{
    Node *current_node = head;     // To Traverse The linked list.
    
    // We keep track of what the previous node is.
    Node *previous_node = NULL;
    for(int i=0;i<n;i++)            // Traverse to the nth node
    {
        previous_node = current_node;       
        current_node = current_node->next;  
    }

    // current_node contains the nth element
    // previous_node contains the (n-1)th element.
    if(n!=0)    // Update (n-1)th node
        previous_node->next = current_node->next;
    else        // Update the head node.
        head = head->next;
    free(current_node);         // Delete the nth node
    return head;                // Return the modified linked list.

}

featured solution by ash1794