simple O(k) Java code(1ms) with explanation


  • 0
    
    	private ListNode rotateRight(ListNode head, int k) {
    		if (head == null) return null;
    		// initialize the two point( k in distance ) and check whether
    		// k is greater than the list length.
    		ListNode p1 = head, p2 = p1, p3 = null;
    		for (int i = 0; i < k; i ++) {
    			p2 = p2.next;
    			if (p2 == null) {
    				k = k % (i + 1);
    				break;
    			}
    		}
    		if (k == 0) return head;
    		p2 = p1;
    		for (int i = 0; i < k; i ++)
    			p2 = p2.next;
    		while (p2.next != null) {
    			p1 = p1.next;
    			p2 = p2.next;
    		}
    		p3 = p1.next;
    		p1.next = null;
    		p2.next = head;
    		return p3;
    	}	
    

Log in to reply
 

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