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

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //迭代法:一次遍历
        if (m == n)
        {
            return head;
        }
        ListNode* pre = nullptr;        //指向待反转结点的前一个结点
        ListNode* cur = head;          //指向待反转结点
        ListNode* nex = nullptr;       //指向待反转结点的下一个结点
        ListNode* mark = nullptr;     //标记m的前一个结点
        int i = 1;
        while (cur && i < m)    //让cur指向m
        {
            mark = cur;
            cur = cur->next;
            ++i;
        }
        while (cur && i <= n)    //反转
        {
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
            ++i;
        }
        //对mark进行分类讨论
        if (mark)    //m不是头结点
        {
            mark->next->next = cur;      //连尾
            mark->next = pre;                //接头
        }
        else    //m是头结点
        {
            head->next = cur;    //连尾
            head = pre;              //接头
        }
        return head;
    }