C++ 12ms Solution with good explanation.


  • 0
    S
    class Solution {
    public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode *p1, *p2, *prev;
        	int j;p1 = p2 = prev = head;
            
                        //corner case where there exists 0 nodes.
    		if (head == NULL) {
    			return NULL;
    		}
                        //case where either number of rotations=0 or there exits only one node.
    		if (k == 0||head->next==NULL) {
    			return head;
    		}
    	        // count the number of nodes.	
            for (j = 0; prev != NULL; j++) {
    			prev = prev->next;
    		}
    		
                        //if number of nodes==number of roations then return head.
    		if (k == j) {
    			return head;
    		}
    	
     /*Here is where i got stuck for a few mins trying to figure this out.
     Say you have a linked liked like 1->2->3 and k=120, you don't have to rotate the list 120 times,instead   
     you divide k/(# of nodes) and obtain the remainder. Which the effective number of times you have to 
     rotate. In this example its 120%3=0,hence rotate it 0 times. */	
    
       if (k>j) {
    			k = k%j;
    			if (k == 0)
    			    return head;
    		}
    		prev = head;
            
        //have pointer p2 advance k times to maintain a distance of k from pointer p1 in the head.
    		for (int i = 1; i < =k; i++) {
    			p2 = p2->next;
    		}
    //This part can be self explanatory. 
    		while (p2->next != NULL) {
    
    			p2 = p2->next;
    			prev = p1;
    			p1 = p1->next;
    		}
    		prev = p1;
    		p1 = p1->next;
    
    		prev->next = NULL;
    		p2->next = head;
    		return p1;
    
    }
    

    };


Log in to reply
 

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