Part 22 of 22 in Linked List - set 01

Problem statement

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.

Input

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.

Output

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)
{

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