61 Rotate List

1. Question

Given a list, rotate the list to the right bykplaces, wherekis non-negative.
Example:
1
Given 1->2->3->4->5->NULL and k= 2,
2
3
return 4->5->1->2->3->NULL.
Copied!

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode rotateRight(ListNode head, int k) {
11
if (head == null || k == 0) {
12
return head;
13
}
14
15
int len = 1;
16
ListNode curNode = head;
17
18
while (curNode.next != null) {
19
curNode = curNode.next;
20
++len;
21
}
22
23
k %= len;
24
curNode.next = head;
25
26
for (int i = 0; i < len - k; i++) {
27
curNode = curNode.next;
28
}
29
30
head = curNode.next;
31
curNode.next = null;
32
return head;
33
}
34
}
Copied!

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)