Share my java solution with explanation

  • 71

    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) {
        if (head==null|| return head;
        ListNode dummy=new ListNode(0);;
        ListNode fast=dummy,slow=dummy;
        int i;
        for (i=0;!=null;i++)//Get the total length ;
        for (int j=i-n%i;j>0;j--) //Get the i-n%i th node;
       ; //Do the rotation;;

  • 2

    why did you use a dummy node?

  • 0

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

    class Solution {
        ListNode* rotateRight(ListNode* head, int k) {
            if (!head) return NULL;
            int len = listLength(head);
            k %= len;
            ListNode* fast = head;
            for (int i = 0; i < k; i++)
                fast = fast -> next;
            ListNode* slow = head;
            while (fast -> next) {
                slow = slow -> next;
                fast = fast -> next; 
            fast -> next = head;
            head = slow -> next;
            slow -> next = NULL; 
            return head;
        int listLength(ListNode* head) {
            int len = 0;
            while (head) {
                head = head -> next;
            return len;

  • 13

    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
    	ListNode fast=head;
    	ListNode slow = head;
    	    fast =;
    	for(int i=size-k%size;i>1;i--) // i>1 because we need to put at the start.
    		slow =;
        // No dummy variable. = head;
    	head =; = null;
    	return head;

  • 0

    Hi @reeclapple! for the third part of your code which is the rotation: I got the following code which basically moves the = 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!

   = null;
   = head;

  • 0
    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) {
    		if(head == null) return head;
    		int length = 0;
    		ListNode node = head;
    		while(node != null){
    			node =;
    		k = k % length;
    		ListNode fpart, lpart;
    		lpart = head;
    		for(int i = 1; i < length - k; i++){
    			head =;
    		fpart =; = null;
    		if(fpart == null) return lpart;
    		node = fpart;
    		while( != null){
    			node =;
    		} = lpart;
    		return fpart;

  • 0


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

  • 0

    @tobelzm I have the same question..

  • 0

    same problem. do you have any idea now?

  • 0

    same problem. do you have any idea now?

Log in to reply

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