题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* successor = nullptr; ListNode* reverseN(ListNode* head, int n) { if (n == 1) { // 记录第 n + 1 个节点 successor = head->next; return head; } // 以 head->next 为起点,需要反转前 n - 1 个节点 ListNode* last = reverseN(head->next, n - 1); head->next->next = head; // 让反转之后的 head 节点和后面的节点连起来 head->next = successor; return last; } ListNode* reverseBetween(ListNode* head, int m, int n) { // write code here if (m == 1) { return reverseN(head, n); } // 前进到反转的起点触发 base case head->next = reverseBetween(head->next, m - 1, n - 1); return head; } };