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.

双指针法

复杂度

时间 O(N) 空间 O(1)

思路

旋转链表的本质，就是把链表的后半部分放到前面来，所以关键在于如何找链表后半部分的起始节点。实际上，我们用一个快指针先走k步，然后快慢指针同时走，这样当快指针到末尾时，慢指针就到链表后半部分的起始节点了。不过，由于k可能大于链表的长度，所以我们要先对k取链表长度的模。要计算链表长度只要遍历一遍链表就行了。

注意

k取余后为0，或者原链表为空的情况下，都要直接返回原链表，不然将慢指针的下一个作为新链表头会出错。

代码

public class Solution {    public ListNode rotateRight(ListNode head, int k) {        ListNode fast = head;        int length = 0;        // 计算链表长度        while(fast != null){length++;fast = fast.next;        }        // 如果不旋转或者原链表为空 则直接返回        if(head == null || k % length == 0){return head;        }        fast = head;        // 让快指针先走k步        for(int i = 0; i < k % length; i++){fast = fast.next;        }         // 找到新头节点的前一个节点        ListNode slow = head;        while(fast.next != null){fast = fast.next;slow = slow.next;        }        // 将后半部分放到前面来        ListNode newHead = slow.next;        slow.next = null;        fast.next = head;        return newHead;    }}