首页 > 代码库 > 第22题 Rotate List

第22题 Rotate List

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:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head==null||head.next==null || n==0) return head;
        ListNode fakeHead = new ListNode(0);
        fakeHead.next=head;
        int length=0;
        ListNode start=fakeHead, end=fakeHead;
        for(int i=0; i<n; i++){
            if(end.next==null) break;
            end=end.next;
            length++;
        }
        if(end.next==null){
            //when n>=length
            //int startPos = (length-n)%length+length;      //Or:
            int startPos=n%length;
            if(startPos==0) return fakeHead.next;
            startPos=length-startPos;
            
            for(int i=0; i<startPos; i++){
                start=start.next;
            }
        }
        else{
            while(end.next!=null){
                start=start.next;
                end=end.next;
            }
        }
        //reorder list  
        end.next=fakeHead.next;
        fakeHead.next=start.next;
        start.next=null;
        return fakeHead.next;
        
        
    }
}
Note:假设end后移n次后end.next还不是null,说明list的长度>n。则将start和end总体后移。

否则,说明list的长度<=n,这时候须要找到rotate的实际次数。对于一个长为length的list,若rotate的次数为length,则结果为原list。所以rotate的实际次数是n%length,若结果为0,则直接返回原list;否则,须要找到对应的start点,即改动list的起始点。

注意代码中

 int startPos = (length-n)%length+length;      
事实上和

int startPos=n%length;
startPos=length-startPos;
一个效果(startPos不为0时)。可是后者比較好理解。

另外一个负数对一个正数取模,计算例如以下:

 result=m%n, where m<=0, n>0

Assume m=xn+result, where x<=0, result<0 and -result<n.

比方(-5)%3。 -5=3*(-1)+(-2)。所以(-5)%3=-2。

第22题 Rotate List