题解 | #牛群的重新排列#

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

问题分析：这道题可以用头插来做，也可以用栈来做，相比上一道要容易些，大致思路和上一个差不多；prev指向第一个翻转结点的前一个，end指向第一个翻转的结点，cur指向翻转的结点，next指向翻转结点的下一个结点，然后对第left到第right个的结点头插，最后在将头插的和未投插的结点连接起来。

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

ListNode* reverseBetween(ListNode* head, int left, int right)
{
    // write code here
    ListNode* newhead = new ListNode(-501);
    newhead->next = head;

    ListNode* prev = newhead; //prev是开始进行翻转的前一个结点
    int n = 1;
    while (n < left)
    {
        prev = prev->next;
        ++n;
    }
    ListNode* cur = prev->next; //cur是需要翻转的结点
    ListNode* next = cur->next; //next是翻转的结点的下一个结点
    ListNode* end = cur; //end是第left个结点
    while (left <= right)
    {
        //头插
        cur->next = prev->next;
        prev->next = cur;
        //更新结点
        cur = next;
        if (next)
            next = next->next;
        ++left;
    }
    //连接
    end->next = cur;

    head = newhead->next;
    delete newhead;

    return head;
}