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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <linux/limits.h>
class Solution {
  public:
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == nullptr ) return nullptr;
	  //创建一个虚拟头结点，方便返回head（可能会修改head的指向）
        auto virhead = new ListNode(MAX_INPUT);
        virhead->next = head;
        ListNode* p = virhead;
        int pos = 0;
        //找到m的前驱
        while (p != nullptr && pos != m - 1) 
        {
            p = p->next;
            ++pos;
        }
        //找到n结点的下一个
        pos = 0;
        ListNode* q = p;
	  //n-m+2 q为m的前驱，到n的下一个，所以+2
        while(q != nullptr && pos != n-m+2)
        {
            q = q->next;
            ++pos;           
        }
        //反转m到n
        ListNode* temp = p->next;
        ListNode* tempnext;
        p->next = q;
        while(temp != q)
        {
            tempnext = temp->next;
            temp->next = p->next;
            p->next = temp;
            temp = tempnext;
        }
        p = virhead->next;
	  //销毁虚拟头结点
        delete (virhead);
        return p;


    }
};