Tuesday, February 11, 2014

Rotate a Linked List

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

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.

void rotateList(Node *&head, int k)
     if (k == 0)

    Node* curr = head;

    int count = 1;
    while (count < k && curr != NULL)
        curr = curr->next;

    if (curr == NULL)

    Node *kthNode = curr;

    while (curr->next != NULL)
        curr = curr->next;

    curr->next = head;
    head = kthNode->next;
    kthNode->next = NULL;

No comments:

Post a Comment