Rotate linked list by K nodes

You are given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer.
i.e. if the given linked list is: 1->2->3->4->5 and k is 3,
the list should be modified to: 4->5->1->2->3.
Assume that k is smaller than the number of nodes in linked list.

Steps:
1) Traverse the list by k nodes.
2) Keep kth node in temp.
3) Travese till end of list and set last node pointer to start.
4) Set kth nodes next to head.
5) Point kth node next to NULL.

void rotate (struct node **head, int k)
{
     if (k == 0)
       return;

    struct node* current = *head;
 
    int count = 1;
    while (count < k && current != NULL)
    {
        current = current->next;
        count++;
    }
 
    if (current == NULL)
        return;
 
    struct node *kthNode = current;
 
    while (current->next != NULL)
        current = current->next;
 
    current->next = *head;
 
    *head = kthNode->next;
    kthNode->next = NULL;
}

Compleixty: O(N)

Output:

Given linked list
1 2 3 4 5
Rotated Linked list
3 4 5 1 2

0 Thoughts on “Rotate linked list by K nodes

  1. This is very well explained.. :)

Leave a Reply to Ankita Jain Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation