题解 | #调整牛群顺序#

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

问题分析：首先找出倒数第 n 个结点，使用快慢指针方法，然后这个倒数第 n 个结点可能是头结点，头结点可能是需要改变的，所以有两种思路：第一种，将改变的结点判断一下，若为头结点，则修改头结点的指针，若不是，则正常处理；第二种，构造一个新的头结点，然后再按正常处理就行。

如下为第二种思路，代码如下：

ListNode* moveNthToEnd(ListNode* head, int n)
{
    // write code here
    if (n == 1)
        return head;

    ListNode* newhead = new ListNode(-1);
    newhead->next = head;
    ListNode* cur = newhead;
    ListNode* prev = newhead, * end = newhead; //prev指向的是交换结点的前一个指针

    //寻找倒数第k个结点使用快慢指针方法，这里end相当于快指针，prev是慢指针
    for (int i = 0; i < n; ++i)
    {
        end = end->next;
    }
    while (end->next)
    {
        prev = prev->next;
        end = end->next;
    }
    //end指向最后一个结点
    cur = prev->next;
    prev->next = cur->next;
    end->next = cur;
    cur->next = nullptr;
  
    head = newhead->next; //头结点可能被改变，所以更新头结点
    delete(newhead);

    return head;
}