Given a list, rotate the list to the right bykplaces, wherekis non-negative.

For example:
Given1->2->3->4->5->NULLandk=2,
return4->5->1->2->3->NULL.

Subscribeto see which companies asked this question.

Hide Tags

Linked List

Two Pointers

Hide Similar Problems

(E) Rotate Array

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null)
            return null;

        if(k == 0)
            return head;

        ListNode tail = null;
        int length = 0;

        //find the last node and the length of list
        //找到最后一个节点，找到list的长度
        ListNode root = head;
        while(root != null){
            length++;
            tail = root;
            root = root.next;
        }

        //reformat the k
        //获得取模后的k
        int kk = k % length;
        System.out.println("length=" + length +",kk=" + kk);
        if(length == 1 || kk == 0)
            return head;

        kk = length - kk;
        //find the new head and the pre node of the new head
        //找到新的头节点，以及头结点前一个（该节点的next需要置为null）
        int i=0;
        ListNode pre = null;
        root = head;
        while(i<kk){
            pre = root;
            root = root.next;
            i++;
        }
        //change the next of the tail node
        //将最后一个节点的next置为之前的head
        tail.next = head;
        //change the next of the pre node of new head
        //将之前头结点的前一个节点的next置为null
        pre.next = null;

        //返回新的头结点
        return root;
    }
}

public ListNode rotateRight(ListNode head, int n) {
    if (head==null||head.next==null) return head;
    ListNode dummy=new ListNode(0);
    dummy.next=head;
    ListNode fast=dummy,slow=dummy;

    int i;
    //通过这一步就得到了长度和最后一个节点
    for (i=0;fast.next!=null;i++)//Get the total length 
        fast=fast.next;

    for (int j=i-n%i;j>0;j--) //Get the i-n%i th node
        slow=slow.next;

    fast.next=dummy.next; //Do the rotation
    dummy.next=slow.next;
    slow.next=null;

    return dummy.next;
}