Leetcode: Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Understand the problem:
The crux of the problem is to understand what is to rotate the list to the right by k places. An easier way to understand the problem is to rotate the tail of the linked list by k places to to the head in counter-clock wise. For e.g. k  = 1,
1->2->3->4->5, becomes 5->1->2->3->4

For k = 2, it becomes 4->5->1->2->3.

So the key of the problem is to find the place where to set the next node as the new head, and linked the old tail to the old head, and break the linked list to the point we are looking for. Note that k could be larger than n since it could be cyclic rotated. 

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || n == 0) {
            return head;
        }
        
        // get the number of nodes of the linked list
        int len = 0;
        ListNode p = head;
        while (p != null) {
            len++;
            p = p.next;
        }
        
        if (len == 1 || n % len == 0) {
            return head;
        }
        
        int steps = len - n % len - 1;
        
        ListNode newHead = head;
        p = head;
        for (int i = 0; i < steps; i++) {
            p = p.next;
        }
        
        newHead = p.next;
        ListNode q = newHead;
        p.next = null;
        
        while(q.next != null) {
            q = q.next;
        }
        q.next = head;
        
        return newHead;
    }
}

Summary:
The problem itself is relatively simple. When doing linked list questions, be careful about the null pointer exception error.

Update on 9/21/15

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k <= 0) {
            return head;
        }
        
        // Step 1: count the length of the list
        int len = getLengthOfList(head);
        if (k % len == 0) {
            return head;
        }
        
        // Step 2: find the nth element from the end
        int n = k % len + 1;
        ListNode slow = head;
        ListNode fast = head;
        int count = 1;
        
        while (count < n) {
            fast = fast.next;
            count++;
        }
        
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // Step 3: rotate to the head
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;
        
        return newHead;
    }
    
    private int getLengthOfList(ListNode head) {
        int len = 0;
        ListNode p = head;
        while (p != null) {
            len++;
            p = p.next;
        }
        
        return len;
    }
}