Rotate List
出处
Given a list, rotate the list to the right by k places, where k is non-negative. e.g: 1->2->3->4->5, k = 2; after rotation: 4->5->1->2->3
Solution
假设链表长度为len,新的链表的尾节点是原链表中第 len-k 个节点。则我们的runner指针需要前进len – k – 1 次,到达的位置即为新链表中的尾节点。同时,下一个节点即为新链表的头结点。
Complexity
时间复杂度 O(n)
Code
Node rotateList(Node head, int k){
if (head == null) return null;
// get the length of the list;
Node tmp = head;
int length = 1;
while (tmp.next != null){
length++;
tmp = tmp.next;
}
// move the pointer to len - k%len -1
k = k % length;
if (k == 0)
return head;
// link the tail to the head
tmp.next = head;
for(int i = 0; i < length - k - 1; i++){
cur = cur.next;
}
head = cur.next;
cur.next = null;
return head;
}