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

/**
 * 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 (head == nullptr) return nullptr;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        cout << dummy->val << endl;

// 改变q也能够改变哨兵结点dummy，让头结点一直保持原样
        ListNode *q = dummy;
        for (int i = 0; i < m-1; ++i)
        {
            q = q->next;
        }
        ListNode *start = q;
        for (int i = m; i <= n; ++i)
        {
            q = q->next;
        }

        ListNode *end = q->next;
        q->next = nullptr;
        ListNode *p = nullptr;
        q = start->next;
        while (q != nullptr)
        {
            ListNode *t = q->next;
            q->next = p;
            p = q;
            q = t;
        }

        start->next = p;
        while (p ->next != nullptr)
        {
            p = p->next;
        }
        p->next = end;
        return dummy->next;
    }
};