LeetCode 61 - 旋转链表

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || !head->next || !k)
            return head;
        ListNode *slow = head, *fast = head;
        int i = 1;
        /* 让快指针先行移动k步 */
        while(i <= k)
        {
            /* 如果已经到底，说明k比链表长度长，此时取余退出循环 */
            if(!fast->next)
            {
                k = k % i;
                continue;
            }
            fast = fast->next;
            i++;
        }

        /* 如果k取余后为0，说明k正好等于链表长度，直接返回 */
        if(!k)
            return head;

        /* 如果不等，说明此时归为了第一种情况，fast从head重新开始走k步（此时k已经取余更新为小于链表长度的值 */
        if(i != k)
        {
            i = 0;
            fast = head;
            while(i < k)
            {
                if(!fast)
                    return head;
                fast = fast->next;
                i++;
            }
        }

        /* 快慢指针同时移动 */
        while(fast->next)
        {
            fast = fast->next;
            slow = slow->next;
        }

        /* 在此处进行旋转，并连接原来的头节点 */
        ListNode *slowNext = slow->next;
        slow->next = nullptr;
        fast->next = head;
        return slowNext;
    }
};