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

考察知识点： 链表、翻转链表

题目分析：

 首先找到left和right所指向的位置，确定翻转链表的边界。如{1,2,3,4,5},2,4

 在找i时可以记录它的前驱节点l，方便在翻转链表后重新插回原链表。j的后继节点r也同样需要记录。这样就可以将关注点放在i～j节点之间。

 然后翻转链表即可。使用一个指针n遍历i～j，需要记录n的前驱prev和后继next节点。

 每次将n->next更新为prev即可翻转，prev更新为n，n更新为next，next再更新为n->next。

 全部翻转完后将翻转后的链表插入回原链表即可。翻转后l后面应插入j，r前应连接i。

 注意l节点可能是nullptr，即i节点是头节点的情况，这种情况下只需要更新head节点即可。

所用语言： C++

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param left int整型 
     * @param right int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // write code here
        if (left == right) return head;
        ListNode *i = head, *j = head;
        ListNode *prev = nullptr;
        for (int k = 1; k < left; k++) {
            prev = i;
            i = i->next;
        }
        for (int k = 1; k < right; k++) {
            j = j->next;
        }
        ListNode *n = i;
        ListNode *next = n->next;
        ListNode *l = prev;
        ListNode *r = j->next;
        prev = nullptr;
        while (n != r) {
            n->next = prev;
            prev = n;
            n = next;
            next = n->next;
        }
        if (l != nullptr) l->next = j;
        else head = j;
        i->next = r;
        return head;
    }
};