# Share my java solution with explanation

• Since n may be a large number compared to the length of list. So we need to know the length of linked list.After that, move the list after the (l-n%l )th node to the front to finish the rotation.

Ex: {1,2,3} k=2 Move the list after the 1st node to the front

Ex: {1,2,3} k=5, In this case Move the list after (3-5%3=1)st node to the front.

So the code has three parts.

1. Get the length

2. Move to the (l-n%l)th node

3)Do the rotation

``````public ListNode rotateRight(ListNode head, int n) {
ListNode dummy=new ListNode(0);
ListNode fast=dummy,slow=dummy;

int i;
for (i=0;fast.next!=null;i++)//Get the total length
fast=fast.next;

for (int j=i-n%i;j>0;j--) //Get the i-n%i th node
slow=slow.next;

fast.next=dummy.next; //Do the rotation
dummy.next=slow.next;
slow.next=null;

return dummy.next;
}``````

• why did you use a dummy node?

• Hi, reeclapple. I implement the same algorithm in C++, and without using the `dummy` node.

``````class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
k %= len;
for (int i = 0; i < k; i++)
fast = fast -> next;
while (fast -> next) {
slow = slow -> next;
fast = fast -> next;
}
slow -> next = NULL;
}
private:
int len = 0;
len++;
}
return len;
}
};``````

• I used your logic and tried to get rid of the extra dummy variable.

``````public static ListNode rotateRight(ListNode head, int k) {
return null;
int size = 1; // since we are already at head node

while(fast.next!=null){
size++;
fast = fast.next;
}

for(int i=size-k%size;i>1;i--) // i>1 because we need to put slow.next at the start.
slow = slow.next;

// No dummy variable.
slow.next = null;

}
``````

• Hi @reeclapple! for the third part of your code which is the rotation: I got the following code which basically moves the fast.next = dummy.next line to the bottom. i dont see why this can't pass since they are doing the same thing, but OJ didnt let me through. Wondering if you could provide some thoughts. Thank you!

``````        dummy.next = slow.next;
slow.next = null;

1. get the total length
2. k = k % length, avoid cycle
3. split list to fpart and lpart
4. move to last element of fpart and assign next as lpart
``````	public ListNode rotateRight(ListNode head, int k) {

int length = 0;
while(node != null){
node = node.next;
length++;
}
k = k % length;

ListNode fpart, lpart;
for(int i = 1; i < length - k; i++){
}

if(fpart == null) return lpart;
node = fpart;
while(node.next != null){
node = node.next;
}
node.next = lpart;

return fpart;
}``````

• @therealfakebatman

But dummy is a nice practice. The logic is more clear with the dummy node.

• @tobelzm I have the same question..

• @tobelzm
same problem. do you have any idea now?

• @c3c
same problem. do you have any idea now?

• Thanks for your idea @reeclapple. I tried for a clean version.

``````class Solution {
public ListNode rotateRight(ListNode head, int k) {
ListNode fake = new ListNode(-1), slow = fake, fast = fake;

int len = 0;
while(fast.next != null){   // fast REACH tail && Count len
fast = fast.next; len++;
}
if(len == 0) return null;   // CHECK null

k %= len;
for(int i=0; i<len-k; i++)  // slow REACH before the rotated point
slow = slow.next;

fast.next = fake.next;      // CONNECT
fake.next = slow.next;
slow.next = null;

return fake.next;
}
}
``````

• @tobelzm Take [1] k = 0 as a example, Or[1, 2] k = 0 as another example, you will understand.
There is a little tricky point in this problem.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.