Rotate List

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

Have you met this question in a real interview? Yes

Example
Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.

Leetcode
Lintcode

Solution:

Because k may be greater the length of the list, we need to caculate the length of the list first.
Then we can say rotate the list by (k % length) places.
Next, we Link the head and tail of the list as a circle.
Continuely, go through (length - k % length) places, and break the connection at that node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*************************************************************************
> File Name: RotateList.java
> Author: Yao Zhang
> Mail: psyyz10@163.com
> Created Time: Wed 18 Nov 16:47:13 2015
************************************************************************/


public class RotateList{
public ListNode rotateRight(ListNode head, int k) {
if (head == null)
return head;

int length = 1;

ListNode current = head;
while (current.next != null){
length++;
current = current.next;
}

current.next = head;
k = length - k % length ;

while (k > 0){
current = current.next;
k--;
}

head = current.next;
current.next = null;

return head;
}
}