题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <cstdlib> #include <stack> 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 //m=n就不用反转了,直接返回 if(m==n){return head;} //在头节点前新建一个节点;方便m=1时操作 ListNode* temphead=new ListNode(-1001); temphead->next=head; ListNode* cur=temphead; //建立左右指针指向反转区间邻居节点 ListNode* leftcur,*rightcur=nullptr; int flag=0; while(cur!=nullptr){ if(flag==m-1){leftcur=cur;} if(flag==n+1){rightcur=cur;break;} flag++; cur=cur->next; } //压入反转区间节点到栈 stack<ListNode*>reversestack; cur=leftcur; cur=cur->next; while(cur!=rightcur) { reversestack.push(cur); cur=cur->next; } //栈弹出反转区间 while(!reversestack.empty()){ leftcur->next=reversestack.top(); reversestack.pop(); leftcur=leftcur->next; } //不要忘记反转后最后一个节点的指向 leftcur->next=rightcur; head=temphead->next; free(temphead); return head; } };