# My clean C++ code, quite standard (find tail and reconnect the list)

• There is no trick for this problem. Some people used slow/fast pointers to find the tail node but I don't see the benefit (in the sense that it doesn't reduce the pointer move op) to do so. So I just used one loop to find the length first.

``````class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {

int len=1; // number of nodes
ListNode *newH, *tail;

while(tail->next)  // get the number of nodes in the list
{
tail = tail->next;
len++;
}

if(k %= len)
{
for(auto i=0; i<len-k; i++) tail = tail->next; // the tail node is the (len-k)-th node (1st node is head)
}
newH = tail->next;
tail->next = NULL;
return newH;
}
};``````

• so good！i like it！

• Came up a solution almost the same as yours so just share here :)

The difference is we don't need to make the circle when k %= length equals 0

``````/**
* Memo: Make the list into a circle if we need to rotate, then rotate to the needed location and break the circle.
* Complex: O(n)
* Runtime: 168ms
* Tests: 230 test cases passed
* Rank: S
* Updated: 2015-06-18
*/
var rotateRight = function(head, k) {
if (!head || !head.next) return head; // no need to rotate if the list is empty or has only one element

var length = 1;
while (tail.next) {
length++;
tail = tail.next;
}

if (k %= length) {
tail.next = head; // make a full circle
for (var i = 0; i < length - k; i++) tail = tail.next; // move to previous node before breaking point
tail.next = null; // break the circle
}
};
``````

• This is my solution. The difference is, when k <= lens, NO need to traverse the lists twice! Only once!
The time consuming is 8ms.

``````class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int lens = 1;
while(k--)
{
if(fast->next)
{
fast = fast->next;
lens ++;
}
else
{
k %= lens;
}
}
while(fast->next)
{
fast = fast->next;
slow = slow->next;
}
slow->next = NULL;
}
};``````

• awesome, this is so clever.

• Clever idea!

• Good solution! It is really clever to circular the link :-)

• The following code is really clever :-)

``````fast = head;
k %= lens; ``````

• Nice idea. thanks for sharing.
my solution based on your idea.

``````ListNode* rotateRight(ListNode* head, int k) {
int len = 1;
while (cur->next && ++len) cur = cur->next;
k = len - k % len;
while (k--) cur = cur->next;
cur->next = nullptr;
}``````

• This post is deleted!

• When the len is big and big and the k is so small ie.. 1,2,3... , your method will not be efficient I think.

• What a coincidence! My solution is same as yours.
class Solution {
public:

``````ListNode* rotateRight(ListNode* head, int k) {
int len = 1;
while (p->next) {
p = p->next;
len++;
}
k %= len;
while (len>k) {
p = p->next;
len--;
}
p->next = NULL;
}
``````

};

• JavaScript:

``````var rotateRight = function(head, k) {
}

var len = 1;
var tail = new ListNode();

while (tail.next) {
tail = tail.next;
len++;
}

k %= len;

if (k) {
for (var i = 0; i < len - k; i++) {
tail = tail.next;
}
}

tail.next = null;
};
``````

• @dong.wang.1694
awesome! This method don't move the value in the memory but only the pointer of the list.

• @SwenZhai , is there any problem related to Linked-list solved by changing the value of the list node ?

• Python translation

``````class Solution(object):
len = 1
while current.next:
current = current.next
len += 1
k = k % len
print(k)
print(len)
for i in range(len-k):
current = current.next
current.next = None
``````

• Here is my solution, which doesn't need to count the length of the list first. Just use faster pointer and slower pointer method, when moving the faster pointer and k is larger than the length of the list, make k = k%length and move from head again. So even if k is far larger than list length, we will go through the list for no more than twice

``````ListNode* rotateRight(ListNode* head, int k) {
for(int i=0;i<k;i++){ // move the faster pointer for k steps first
if(p1->next) p1 = p1->next;
else{
k = k%(i+1);//if k is greater than the length of the list, make k = k%length
i = -1; // and count from the beginning again
}
}
while(p1->next!=NULL){
p1 = p1->next;
p2 = p2->next;
}
p2->next = NULL;
}
``````

• @dong.wang.1694 The fast and slow pointer method has some advantages that is not so obvious. It is one-shot traverse. Think about the situation when device is lack of memory. The time consumption is mainly related to data transfer from disk to memory which means One-shot traverse is definitely faster than two or more traverses. In this way, two pointers method seems to outperform your algorithm. However, under the hypothesis that RAM is sufficient, two approaches are almost equivalent. I prefer your concise solution.

• C++ Version

``````class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int len = 1;
while (p->next) {
++len;
p = p->next;
}