Share my java solution with explanation


  • 71
    R

    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||head.next==null) return head;
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        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;
    }

  • 2
    D

    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 {
    public:
        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;
        }
    private:
        int listLength(ListNode* head) {
            int len = 0;
            while (head) {
                len++;
                head = head -> next;
            }
            return len;
        }
    };

  • 13
    T

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

    public static ListNode rotateRight(ListNode head, int k) {
    	if(head==null)
            return null;
    	int size = 1; // since we are already at head node
    	ListNode fast=head;
    	ListNode slow = head;
    	
    	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.
    	fast.next = head;
    	head = slow.next;
    	slow.next = null;
    	
    	return head;
    }
    

  • 0
    T

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

  • 0
    H

    @therealfakebatman

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


  • 0

    @tobelzm I have the same question..


  • 0
    H

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


  • 0
    H

    @c3c
    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.