Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given
return
Given
1->2->3->4->5->NULL
and k = 2
,return
4->5->1->2->3->NULL
.
Solution:
First of all, we have to find the rotation point, eg. in the example given in the problem, the rotation position is 3. Using the runner- walker technique, let runner run k step first, then, walker start to walk, when runner hit the end, walker will be k steps away from the end, which is the rotation point we want to find.
Tips:
The tricky part for this problem, is that k may exceed the length of the list. If so, we have to use k mod the length of list and then find the rotation position.
public ListNode rotateRight(ListNode head, int n) {
if(head==null || head.next==null || n==0) return head;
ListNode preDummy=new ListNode(0);
preDummy.next=head;
ListNode runner=preDummy;
int i=0;
for(;i<=n && runner!=null;i++){
runner=runner.next;
}
if(runner==null) {
n=n%(i-1);
if(n==0) return head;
runner=preDummy;
for(int j=0;j<=n;j++) runner=runner.next;
}
ListNode pre=head;
while(runner.next!=null){
pre=pre.next;
runner=runner.next;
}
runner.next=head;
preDummy.next=pre.next;
pre.next=null;
return preDummy.next;
}
No comments:
Post a Comment