```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
ListNode *current = head;
int count = 0;
// create a map
map<int , ListNode*> mymap;
if(current == NULL)
return current;
while(current != NULL){
// count = 0;
mymap.insert(pair<int , ListNode*>(count , current));
count++;
current = current->next;
}
cout << "Length of list " << count << endl;
// count is the length of the list
if(k == count)
return head;
// this check is because when K is very large it will round off
if(k > count)
k %= count;
map<int , ListNode *> :: iterator prev = mymap.find(count-k-1);
map<int , ListNode *> :: iterator last = mymap.find(count-1);
last->second->next = head;
head = prev->second->next;
prev->second->next = NULL;
return head;
}
};
```

I used hashtable to solve this.. O(n).. Can we solve better? Please suggest

We can also solve this w/0 hash table.. just iterate and count the number of nodes.

Store the last node pointer and iterate again to reach node (count-k+1) from start.. after that follow the same logic I used. it will take O(2n) = O(n)