Insert a node after the n-th node from the end

Insert a node x after the nth node from the end in the given singly linked list. It is guaranteed that the list contains the nth node from the end. Also 1 <= n.

Examples:

Input : list: 1->3->4->5
        n = 4, x = 2
Output : 1->2->3->4->5
4th node from the end is 1 and
insertion has been done after this node.

Input : list: 10->8->3->12->5->18
        n = 2, x = 11
Output : 10->8->3->12->5->11->18

Method 2 (Single traversal):
This method uses two pointers, one is slow_ptr and the other is fast_ptr. First move the fast_ptr up to the nth node from the beginning. Make the slow_ptr point to the 1st node of the list. Now, simultaneously move both the pointers until fast_ptr points to the last node. At this point the slow_ptr will be pointing to the nth node from the end. Insert the new node after this node. This method requires single traversal of the list.

struct Node {

    int data;

    Node* next;

};




void insertAfterNthNode(Node* head, int n, int x)

{

    if (head == NULL)

        return;

    // get a new node for the value 'x'

    Node* newNode = getNode(x);

    // Initializing the slow and fast pointers

    Node* slow_ptr = head;

    Node* fast_ptr = head;

    // move 'fast_ptr' to point to the nth node

    // from the beginning

    for (int i = 1; i <= n - 1; i++)

        fast_ptr = fast_ptr->next;

    // iterate until 'fast_ptr' points to the

    // last node

    while (fast_ptr->next != NULL) {

        // move both the pointers to the

        // respective next nodes

        slow_ptr = slow_ptr->next;

        fast_ptr = fast_ptr->next;

    }

    // insert the 'newNode' by making the

    // necessary adjustment in the links

    newNode->next = slow_ptr->next;

    slow_ptr->next = newNode;

}