题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <cstddef> #include <iostream> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ pair<ListNode*, ListNode*> reverseHeadTail(ListNode* head, ListNode* tail) { ListNode* pre = new ListNode(-1); ListNode* cur = head; while (cur != tail) { ListNode* tmp = cur; cur = cur->next; tmp->next = pre; pre = tmp; } cur->next = pre; return {cur, head}; } ListNode* reverseBetween(ListNode* head, int m, int n) { // write code here if (head == NULL) { return nullptr; } if (m == n) { return head; } ListNode* old_pre = new ListNode(0); old_pre->next = head; ListNode* pre = new ListNode(-2); ListNode* cur = head; pre->next = cur; for (int i = 0; i <m-1; i++) { pre = cur; cur = cur->next; } //cur为第m个节点。pre为cur节点的前一个节点。 cout<<"oldhead"<<cur->val<<endl; ListNode* node_m = cur; //第m个节点 ListNode* node_n = cur; for(int i = 0; i<n-m;i++) { cur = cur->next; } node_n = cur; //第n个节点 ListNode* node_n_next = node_n->next; //第n个节点的下一个节点 cout<<"node_n"<<node_n->val<<endl; auto res = reverseHeadTail(node_m, node_n); cout<<"res.first"<<res.first->val<<endl; cout<<"res.second"<<res.second->val<<endl; cout<<pre->val<<endl; cout<<"node_m.val"<<node_m->val<<endl; pre->next = res.first; res.second->next = node_n_next; if(res.second == head) { return res.first; } return head; } };
我终于做出来了。经过了好长时间的debug, 终于做出来了!!!!
核心思路是:先定位到第m个节点和第n个节点,然后将这一段链表传入进行翻转,再进行接入原来链表。
主要卡壳的地方是:原始链表的头节点如果变成了尾节点,需要做特殊判断,而不是一概返回头节点。
时隔3个月,再次开始刷题,感觉很不错。以后可以通过刷题来娱乐啦!!!不用通过刷题找工作啦!!!!