题解 | #链表内指定区间反转#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n || head == nullptr) {	//如果链表为空，或者交换同一个节点
            return head;
        }
        ListNode* reversedHead, *reversedEnd;	//用来记录反转后链表的头节点和尾节点
        ListNode* forward;	//记录首个反转节点的前一个节点
        if (m == 1) {	//如果首个反转节点就是原链表的头节点
            forward = nullptr;
            reversedEnd = head;
            reversedHead = head;
        } else {
            ListNode* tmp = head;
            for (int i = 0; i < m - 2; i++) {
                tmp = tmp->next;
            }
            forward = tmp;	//记录首个反转节点的前一个节点
            reversedEnd = forward->next;	//反转后链表的尾节点节点=首个反转节点
            reversedHead = forward->next;	//反转后链表的头节点=首个反转节点
        }
        ListNode* p = reversedEnd->next;	//第二个个反转节点
        for (int i = 0; i < n - m; i++) {
            ListNode* q = p;
            p = p->next;
            q->next = reversedHead;
            reversedHead = q;
        }
        if (forward == nullptr) {
            if (p == nullptr) {
                reversedEnd->next = nullptr;
            } else {
                reversedEnd->next = p;
            }
            return reversedHead;
        } else {
            forward->next = reversedHead;
            if (p == nullptr) {
                reversedEnd->next = nullptr;
            } else {
                reversedEnd->next = p;
            }
            return head;
        }
    }
};