Sunday, March 8, 2015

61. Rotate List Leetcode Java

Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
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