题目链接：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.

这道题的要求是向右旋转链表k步。

其实就是把链表后面l-k个节点放到前面，可以采用快慢指针处理。不过当k大于链表长度l的时候，就会出现问题。这时需要做一点点处理，就是当快指针f指向最后节点后，下一次令其指向头节点，这样问题就解决了。这样的时间复杂度是O(k)，因此，当k非常大的时候，会TLE。

考虑到k大于l的时候，可以令k对l取模处理。因此，先计算链表长度，同是令p指向链表最后节点。接下来k对l取模，再令q从头节点往后移动l-k步，这样q就指向要旋转的位置。最后将q后面的节点放到前面即可。

假设k=2，加头之后链表为：
h -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL。

领p指向链表最后节点，q指向要旋转的位置，即：
h -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
                    ^         ^
                    |         |
                    q         p

接下来把q后面的节点放到前面：
h -> 0 -> 4 -> 5 -> 1 -> 2 -> 3 -> NULL
               ^              ^
               |              |
               p              q

处理的时候，同样先对链表加头，方便处理，类似于Remove Nth Node From End of List、Swap Nodes in Pairs、Reverse Nodes in k-Group，同样先对链表加头处理。

时间复杂度：O(l)（l是链表长度）

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution
{
public:
    ListNode *rotateRight(ListNode *head, int k)
    {
        if(head == NULL)
            return NULL;
        
        // 链表加头，方便处理
        ListNode *h = new ListNode(0), *p, *q;
        h -> next = head;
        
        int l = 0;
        // p指向最后节点
        for(p = h; p -> next != NULL; ++ l, p = p -> next); 
        // q指向要要旋转位置，即旋转后最后节点
        for(q = h, k = l - k % l; k > 0; -- k, q = q -> next); 
        
        // 把链表后半段放到前面
        p -> next = h -> next;
        h ->next = q -> next;
        q -> next = NULL;
        
        return h -> next;
    }
};