Insert node into the middle of the linked list

Given a linked list containing n nodes. The problem is to insert a new node with data x at the middle of the list. If n is even, then insert the new node after the (n/2)th node, else insert the new node after the (n+1)/2th node.

Examples:

Input : list: 1->2->4->5
        x = 3
Output : 1->2->3->4->5

Input : list: 5->10->4->32->16
        x = 41
Output : 5->10->4->41->32->16

(Using two pointers)

void insertAtMid(Node** head_ref, int x)

{

    // if list is empty

    if (*head_ref == NULL)

        *head_ref = getNode(x);

 

    else {

        // get a new node

        Node* newNode = getNode(x);

 

        // assign values to the slow and fast

        // pointers

        Node* slow = *head_ref;

        Node* fast = (*head_ref)->next;

 

        while (fast && fast->next) {

 

            // move slow pointer to next node

            slow = slow->next;

 

            // move fast pointer two nodes at a time

            fast = fast->next->next;

        }

 

        // insert the 'newNode' and adjust the

        // required links

        newNode->next = slow->next;

        slow->next = newNode;

    }

}