[LeetCode] Rotate List (Java)

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.

Analysis

This problem is not so difficult. We can use two pointers, a fast pointer and a slow pointer, to achieve this. However, there are some corner cases in this problem which needs to be careful.

Take 1 -> 2 -> 3 -> 4 -> 5 as an example. Now k is 2. Our fast pointer will be pointing to 3, and the slow pointer will be pointing to 1, which is 2 steps slow. And it will be easy to transform the list to what we want if we have such pointers.

Code

public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || n == 0)
            return head;
        ListNode slow = head;
        ListNode fast = head;
        while (n > 0) {
            n--;
            fast = fast.next;
            if (fast == null)
                fast = head;
        }
        if (fast == null || slow == fast)
            return head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;
        return newHead;
    }
}

public class Solution {

public ListNode rotateRight(ListNode head, int n) {

if (head == null || n == 0)

return head;

ListNode slow = head;

ListNode fast = head;

while (n > 0) {

n--;

fast = fast.next;

if (fast == null)

fast = head;

}

if (fast == null || slow == fast)

return head;

while (fast.next != null) {

fast = fast.next;

slow = slow.next;

}

ListNode newHead = slow.next;

slow.next = null;

fast.next = head;

return newHead;

}

Complexity

The complexity is O(n + k).