题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <bits/types/struct_tm.h> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* reverseBetween(ListNode* head, int m, int n) { // write code here if (head == nullptr) { return nullptr; } // m和n判断 if (m <= 0 || m > n ) { return nullptr; } else if (m == n) { return head; } else { // 0 < m < n // 为了方便,在链表前加一个头节点pre_head ListNode* pre_head = new ListNode(-1); pre_head->next = head; // 指针 ListNode* mPre = pre_head; // 保存第m-1个节点 for (int i = 0; i < m - 1; i++) { mPre = mPre->next; } ListNode* mPtr = mPre->next; // 保存第m个节点,待取待插节点前一个节点 ListNode* tmp = mPtr->next; // 待取待插节点 for (int i = m; i < n && tmp != nullptr; i++) { // 此时可能出现n>size的情况 mPtr->next = tmp->next; // 取下 tmp->next = mPre->next; // 前插 mPre->next = tmp; tmp = mPtr->next; // tmp更新,mPtr不变 } return pre_head->next; } return head; } };