RotateList [source code]

public class RotateList {
static
/******************************************************************************/
class Solution {
    public ListNode rotateRight(ListNode head, int _k) {
        if (head == null || head.next == null || _k == 0)
            return head;
        ListNode dummy = new ListNode (0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        int k = _k;
        while (k > 0) {
            if ((fast = fast.next) == null) {
                return rotateRight (head, _k % (_k - k));
            }
            k--;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        ListNode res = slow.next;
        slow.next = null;
        fast.next = dummy.next;
        dummy.next = null;
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RotateList.Solution tester = new RotateList.Solution();
        int[][] inputs = {
            {1,2,3,4,5}, {2}, {4,5,1,2,3},
            {1,2}, {3}, {2,1},
            {}, {1}, {},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            ListNode head = ListNode.buildListNode (inputs[3 * i]);
            ListNode ans = ListNode.buildListNode (inputs[3 * i + 2]);
            int k = inputs[3 * i + 1][0];
            System.out.println (Printer.separator ());
            String input_str = ListNode.serialize (head), ans_str = ListNode.serialize (ans);
            String output_str = ListNode.serialize (tester.rotateRight (head, k));
            System.out.printf ("%s and %d -> %s, expected: %s\n", 
                input_str, k, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
            );
        }
    }
}

list的题目, 那么inverse和快慢指针是很常见的小技巧, 脑子里有一个印象, 不知道这题能不能用到;

另外, 熟悉一个表达方式:

rotate the list to the right by k places

意思是右边半段的长度是k;

稍微想了一下, 感觉这题其实就是一个等间隔快慢指针的思路, 前面被坑过两次, 这次不会被坑了; 这种题目因为实际上N是未知的(规定只能1pass), 所以我们不知道N, 只知道K;

另外, dummy head, pre-leaf termination, 这些都是LinkedList题目里面很常见的小技巧了;

感觉写的主逻辑是没有问题的, 但是被test2给break的很烦人, 好像K超过list长度的时候, 必须得手动找到N然后取模; 很不想这么做, 因为这样就不是1pass了; 后来想了一个折中的办法: 判断出来K超界的时候, 再去重新调用一个取模之后的invocation.

后来发现这个办法其实应该是最优的办法了, 因为实际上, 当你发现你超界的时候, 你就已经知道N了, 所以实际上根本不需要专门多走一个pass再来找N;

最后的速度是17ms (31%), 还可以;

linkedlist: input null

好像LinkedList的题目里面, input是Null的Corner Case特别多, 不知道是为什么, 是因为是自定义结构的关系吗? 反正以后碰到这种题目长一个心眼;

没有editorial;

@dong.wang.1694 said in My clean C++ code, quite standard (find tail and reconnect the list):

There is no trick for this problem. Some people used slow/fast pointers to find the tail node but I don't see the benefit (in the sense that it doesn't reduce the pointer move op) to do so. So I just used one loop to find the length first.

class Solution {  
public:  
    ListNode* rotateRight(ListNode* head, int k) {  
        if(!head) return head;  

        int len=1; // number of nodes  
        ListNode *newH, *tail;  
        newH=tail=head;  

        while(tail->next)  // get the number of nodes in the list  
        {  
            tail = tail->next;  
            len++;  
        }  
        tail->next = head; // circle the link  

        if(k %= len)   
        {  
            for(auto i=0; i<len-k; i++) tail = tail->next; // the tail node is the (len-k)-th node (1st node is head)  
        }  
        newH = tail->next;   
        tail->next = NULL;  
        return newH;  
    }  
};

他这个观点是错误的, 我认为我的算法average肯定比他的更快;

@fastcode said in My clean C++ code, quite standard (find tail and reconnect the list):

This is my solution. The difference is, when k <= lens, NO need to traverse the lists twice! Only once!
The time consuming is 8ms.

class Solution {  
public:  
    ListNode* rotateRight(ListNode* head, int k) {  
        if(!k || !head || !head->next)  
            return head;  
        ListNode *fast = head;  
        int lens = 1;  
        while(k--)  
        {  
            if(fast->next)  
            {  
                fast = fast->next;  
                lens ++;  
            }  
            else  
            {  
                fast = head;  
                k %= lens;  
            }  
        }  
        if(fast == head)  
            return head;  
        ListNode *slow = head;  
        while(fast->next)  
        {  
            fast = fast->next;  
            slow = slow->next;  
        }  
        ListNode *newhead = slow->next;  
        slow->next = NULL;  
        fast->next = head;  
        return newhead;  
    }  
};

这个算是开窍的; 他处理的思路跟我实际上是类似的;

当K超界的时候, 官方给出的解释:

@1337c0d3r said in What to do when k is greater than size of list ?:

Let's 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.

@wangdingqiao said in What to do when k is greater than size of list ?:

@introom rotate could be better explained as "shift to right".

所以这个modN并不是一个很trivial的东西, 而是实际上你可以自己证明的; 这里也是熟悉一下rotate的定义;

@mo10 said in Clean Java Solution with Brief Explanation:

The basic idea is to link the tail of the list with the head, make it a cycle. Then count to the rotate point and cut it.

    if (head == null)  
            return head;  

        ListNode copyHead = head;  

        int len = 1;  
        while (copyHead.next != null) {  
            copyHead = copyHead.next;  
            len++;  
        }  

        copyHead.next = head;  

        for (int i = len - k % len; i > 1; i--)  
            head = head.next;  

        copyHead = head.next;  
        head.next = null;  

        return copyHead;  
    }

好像都是这个思路; 说起来很好听, cycle啊, 首尾相连啊, 其实本质还是就是几个关键位置的指针操作, 知道怎么做就行了, 用一个具体的例子来帮助开发;

discussion基本就都大同小异了, 好像很少很少人意识到eager calculate length是有害处的;

submission最优解, 其实基本就是波动内快一点;

class Solution {  
    public ListNode rotateRight(ListNode head, int k) {  
        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-k%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;  
    }  
}

还是一开始就算length的方法;

Problem Description

Given a list, rotate the list to the right by k places, where k is non-negative.

Example:

Given 1->2->3->4->5->NULL and k = 2,  

return 4->5->1->2->3->NULL.

Difficulty:Medium
Total Accepted:129.9K
Total Submissions:532K
Contributor:LeetCode
Related Topics
linked listtwo pointers
Similar Questions
Rotate ArraySplit Linked List in Parts