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
This is very well explained..