Rotate List

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.

Naive Way: 这里联想到了找链表的中点的方法 （龟兔赛跑的启示）。两个指针，如果一个指针一次走一步，一个指针一次走两步，一直走知道某一个遇到null, 走的慢的指针就会正好走到链表的中点。这里也可以用。先把第二个指针走出k步，然后两个指针同时往前走，第二个指针遇到null的时候，第一个指针正好走到我们想要做为新head的地方，再把原来的头接到第二个指针的尾部。

这里我自己做这种指针链表的题目喜欢新设一个头，相当于增加了一个-1的位置，可以避免head=null单独写，正常步数循环的情况会获得父节点instead of子节点，感觉这样方便点。

实际做的时候发现循环到头会自动从head开始继续循环数，所以添加让兔子自动从尾部找到头部的条件。这也是自己没读懂题意。

算法复杂度是O(max(l,n))

/**
 * 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) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode hare = newHead;
        ListNode tortoise = hare;
        int i = 0;
        while(i < n){
            if(hare.next==null)
                hare = newHead;
            hare = hare.next;
            i++;
        }
        if(hare==tortoise){return newHead.next;}
        while(hare!=null && hare.next!=null){
            tortoise = tortoise.next;
            hare = hare.next;
        }
        if(tortoise!=newHead){
            newHead.next = tortoise.next;
            hare.next = head;
            tortoise.next=null;
        }
        return newHead.next;
    }
}


Improved Way: 由于运行时间排的很靠后，有必要思考一下这样的做法是不是好了。如果不需要把头尾相接似乎很方便，那是不是先令n = n%l （l为链表长度)呢？这样试了试。居然运行时间提高了很多。但方法没变化的。

算法复杂度是O(min(l,n))

public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode hare = newHead;
        ListNode tortoise = hare;
        int i = 0,length = 0;
        while(hare.next!=null){
            hare = hare.next;
            length++;
        }
        hare = tortoise;
        while(i < (length==0?0:n%length)){
            hare = hare.next;
            i++;
        }
        if(hare==tortoise){return newHead.next;}
        while(hare!=null && hare.next!=null){
            tortoise = tortoise.next;
            hare = hare.next;
        }
        if(tortoise!=newHead){
            newHead.next = tortoise.next;
            hare.next = head;
            tortoise.next=null;
        }
        return newHead.next;
    }
}


后来在discuss上又看到一个比较好的点子，先把链表连成一个圈，然后循环跳步，最后再断开。但实际运行起来发现是完全一样的，只不过连成圈将 n > length的情况包括进去，和我的第一种方法是一样的。