题解 | #牛群旋转#

考察的知识点：与链表有关的题基本都是插入，删除，交换顺序等，解决这些问题通常将链表的指针进行修改。

问题分析：将链表向右移动 k 个位置，头结点就变成原来链表的倒数第k个结点，所以可以用快慢指针，找出倒数第k个位置的结点，然后将链表重新连接起来。倒数第k个位置结点的前一个结点的next需要修改为空，所以直接找倒数第k+1个结点。

本题解析所用的编程语言：c++

ListNode* rotateLeft(ListNode* head, int k)
{
    //k可能比链表的长度大，所以先将k取余
    ListNode* cur = head;
    int length = 0;
    while (cur)
    {
        ++length;
        cur = cur->next;
    }
    k %= length;
    //快慢指针寻找第k+1个结点的位置
    ListNode* fast = head, * slow = head;
    while (k--)
    {
        fast = fast->next;
    }
    while (fast->next)
    {
        fast = fast->next;
        slow = slow->next;
    }
    //将链表重新进行连接
    fast->next = head;
    head = slow->next;
    slow->next = nullptr;

    return head;
}