Rotate a Linked List

Problem:

Given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer.

Approach:

To rotate the linked list, we need to change next of kth node to NULL, next of last node to previous head node, and finally change head to (k+1)th node. So we need to get hold of three nodes: kth node, (k+1)th node and last node.

Solution:

void rotateList(Node *&head, int k)

{

     if (k == 0)

       return;

    Node* curr = head;

    int count = 1;

    while (count < k && curr != NULL)

    {

        curr = curr->next;

        count++;

    }

    if (curr == NULL)

        return;

    Node *kthNode = curr;

    while (curr->next != NULL)

        curr = curr->next;

    curr->next = head;

    head = kthNode->next;

    kthNode->next = NULL;

}