Clean Java Solution with Brief Explanation


  • 26
    M

    The basic idea is to link the tail of the list with the head, make it a cycle. Then count to the rotate point and cut it.

    if (head == null)
    		return head;
    	
    	ListNode copyHead = head;
    	
    	int len = 1;
    	while (copyHead.next != null) {
    		copyHead = copyHead.next;
    		len++;
    	}
    	
    	copyHead.next = head;
    	
    	for (int i = len - k % len; i > 1; i--)
    		head = head.next;
    
    	copyHead = head.next;
    	head.next = null;
    
    	return copyHead;
    }

  • 0
    G

    Thank you for this neat solution!


  • 0

    @mo10 It's a good solution. Sometimes I cannot write the for loop part when rotate the list since I am quite sure how many steps should I rotate.


  • 0

    Similar solution:

    public class Solution {
      public ListNode rotateRight(ListNode head, int k) {
        if (head != null) {
          ListNode kth = head;
          for (int size = size(head), i = (k % size) + 1; i < size; i++)
            kth = kth.next;
          
          ListNode end = kth;
          while (end.next != null)
            end = end.next;
         
          end.next = head;
          head = kth.next;
          kth.next = null;
        }
        return head;
      }
      private static int size(ListNode head) {
        int result = 0;
        for (; head != null; head = head.next)
          result++;
        return result;
      }
    }
    

Log in to reply
 

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