Rotate List
Source
- lintcode: Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
Example
Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param head: the List
* @param k: rotate to the right k places
* @return: the list after rotation
*/
public ListNode rotateRight(ListNode head, int n) {
int len = 0;
ListNode cur = head;
while(cur!=null){
len++;
cur = cur.next;
}
if(len==0 || n%len==0) return head;
//if n>len, then find the mod of n.
n %= len;
//find the distance of two pointers
ListNode slow = head;
ListNode fast = head;
int len1 = 1;
while(len1<=n){
fast = fast.next;
len1++;
}
//walk both pointers forward until the fast pointer reach the end.
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
ListNode tmp = slow.next;
slow.next = null;
fast.next = head;
head=tmp;
return head;
}
}