首页 > 代码库 > 【LeetCode】Rotate List

【LeetCode】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.

 

start with an example.

Given [0,1,2], rotate 1 steps to the right -> [2,0,1].

Given [0,1,2], rotate 2 steps to the right -> [1,2,0].

Given [0,1,2], rotate 3 steps to the right -> [0,1,2].

Given [0,1,2], rotate 4 steps to the right -> [2,0,1].

So, no matter how big K, the number of steps is, the result is always the same as rotating K % n steps to the right.

public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head==null||head.next==null||n==0)
            return head;
        int len = 0;
        ListNode root = head;
        while(root!=null){
            root=root.next;
            len++;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        int i=n%len;
        if(i==0)
            return head;
        while(i>0&&fast!=null){
            fast=fast.next;
            i--;
        }
        
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
            
        ListNode tem = slow.next;
        fast.next=head;
        slow.next=null;
        return tem;
            
        
    }
}