Leetcode and Lintcode

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;
    }    
}