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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* list, int m, int n) {
        // write code here
        ListNode dummy(0), *head = &dummy, *rear = &dummy;

        int cnt = 1;
        while (list) {
            ListNode* p = list;
            list = list->next;
            p->next = nullptr;

            if (cnt < m || cnt > n) {
                // 尾插法
                rear->next = p;
                rear = p;

				 // 每次尾插都需要更新头指针
                head = p;
            } else {
                // 头插法
                p->next = head->next;
                head->next = p;

				// 仅第一次头插需要更新尾指针
                if (cnt == m) {
                    rear = p;
                }
            }

            ++cnt;
        }

        return dummy.next;
    }
};