旋转链表(所有元素往右移) rotate list

［抄题］：

给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数

样例

给出链表1->2->3->4->5->null和k=2

返回4->5->1->2->3->null

［思维问题］：

就是两条线段的变种，想不到联系

［一句话思路］：

用线段找到位置n，然后连一下

［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

连接的时候：

head.next = dummy.next;
dummy.next = tail;（错了）

1->2->3->2->1->null

1
wrong：

2->null
right：

1->1->2->3->2->null
［二刷］：

1. 因为 head = dummy;往前移动了一位，快指针退出的条件是后一位非空while(head.next != null)
2. tail = dummy;慢指针一定要初始化为dummy
3. 
［总结］：

   if (head == null) {
   return null;
   }

头节点判断空没写就全错了，自己掂量着办吧

［复杂度］：Time complexity: O(n) Space complexity: O(1)

［英文数据结构，为什么不用别的数据结构］：

［其他解法］：

［Follow Up］：

［题目变变变］：

Search in Rotated Sorted Array,   在重复或者不重复的旋转数组中找数，或者求恢复。本题只讨论旋转数组是怎么制造出来的。

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    /*

     * @param head: the List

     * @param k: rotate to the right k places

     * @return: the list after rotation

     */

     //calculate

        private int getLength(ListNode head) {

            if (head == null) {

                return 0;

            }

            int index = 0;

            while(head != null) {

                index++;

                head = head.next;

            }

            return index;

        }

    public ListNode rotateRight(ListNode head, int k) {

        if (head == null) {

            return null;

        }//

        //find n

        int length = getLength(head);

        k = k % length;

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        head = dummy;

        ListNode tail = dummy;

        for(int i = 0; i < k; i++){

            head = head.next;

        }

        //ListNode tail = dummy;

        while(head.next != null) {

            head = head.next;

            tail = tail.next;

        }

        //join up

        head.next = dummy.next;

        dummy.next = tail.next;

        tail.next = null;

        return dummy.next;

    }

}