Given a list, rotate the list to the right by

kplaces, wherekis non-negative.For example:

Given`1->2->3->4->5->NULL`

andk=`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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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).

Pingback: Rotate List – therasablog()