当前位置：首页 > news >正文

BM2 链表内指定区间反转，为什么链表要new一个结点？

news 2025/8/11 22:58:09

链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)

思路就是，把需要反转的结点放入栈中，然后在弹出来。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/#include<stack>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/ListNode* reverseBetween(ListNode* head, int m, int n) {stack<int>s;int cnt=1;ListNode* pre = head;//前一个结点ListNode* cur = head;//当前节点ListNode* res = head;//如果从头节点开始反转，需要重新弄一个头节点以便返回iListNode* tmp = head;//临时结点ListNode T(0);if (m == 1){while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}ListNode*T = new ListNode(s.top());res = T;tmp = res;s.pop();while (!s.empty()){ListNode*T = new ListNode(s.top());tmp->next = T;s.pop();tmp = tmp->next;}while (cur){tmp->next = cur;tmp=cur;cur = cur->next;}return res;}else{while (cnt != m)//这个while世找到m{cnt++;pre = cur;cur = cur->next;}while (cnt <=  n)//入栈{s.push(cur->val);cnt++;cur = cur->next;}//cout<<cur->val<<endl;while (!s.empty())//重新连接{//cout<<s.top()<<endl;ListNode*T = new ListNode(s.top());pre->next = T;s.pop();pre = pre->next;//cout<<pre->val<<endl;}//cout<<pre->val<<endl;while (cur)//连n之后的{pre->next = cur;pre=cur;//cout<<pre->val<<endl;cur = cur->next;}return head;}// write code here}
};

下面有一个错误代码，与上面不一的地方在于

class Solution {
public:ListNode* reverseBetween(ListNode* head, int m, int n) {stack<int>s;int cnt=1;ListNode* pre = head;ListNode* cur= head;ListNode *res=head;ListNode* tmp=head;if (m == 1){while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}res = &ListNode(s.top());tmp = res;s.pop();while (!s.empty()){tmp->next = &ListNode(s.top());s.pop();tmp = tmp->next;}while (cur){tmp->next = cur;cur = cur->next;}return res;}else{while (cnt != m){cnt++;pre = cur;cur = cur->next;}while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}while (!s.empty()){pre->next = &ListNode(s.top());s.pop();pre = pre->next;}while (cur){tmp->next = cur;cur = cur->next;}return head;}// write code here}
}

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/#include<stack>
ListNode T(0);
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/ListNode* reverseBetween(ListNode* head, int m, int n) {stack<int>s;int cnt=1;ListNode* pre = head;ListNode* cur = head;ListNode* res = head;ListNode* tmp = head;//ListNode T(0);if (m == 1){while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}T=ListNode(s.top());res = &T;tmp = res;s.pop();while (!s.empty()){T=ListNode(s.top());tmp->next = &T;s.pop();tmp = tmp->next;}while (cur){tmp->next = cur;cur = cur->next;}return res;}else{while (cnt != m){cnt++;pre = cur;cur = cur->next;}while (cnt <= n){s.push(cur->val);cnt++;cur = cur->next;}//cout<<cur->val<<endl;while (!s.empty()){//cout<<s.top()<<endl;T=ListNode(s.top());pre->next = &T;s.pop();pre = pre->next;//cout<<pre->val<<endl;}//cout<<pre->val<<endl;while (cur){pre->next = cur;pre=cur;//cout<<pre->val<<endl;cur = cur->next;}return head;}// write code here}
};

一个是new一个结点，另一个是建一个结点然后取地址，错误的代码在于，

就是错误代码，我想的是自己创的局部变量T，这个对象每次都是新的，结果在VS2022上调试，一步步发现，原来每次新建的T居然是一个地址！！因为链表里已经加入了之前的T的这个地址，这直接导致链表发生错误，以第一个用例为例，本意是想实现1-4-3-2，结果最后只有1-2

因为在循环时，首先是1-4，在创建3这个节点时，由于是4的地址，所以就把4覆盖了，输出1-3,而不是1-4-3.
链表申请新节点要new。这样每次地址都不一样就连起来了。

下面讲一种，加入一个虚拟节点(哨兵)的做法，之所以这样是可以当从头节点开始转变时，代码不用特判。

/*** 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* head, int m, int n) {ListNode* res=new ListNode(0);//虚拟节点res->next=head;ListNode* pre=res;ListNode* cur=head;ListNode* beg=head;ListNode* en=head;ListNode* tmp;for(int i=1;i<m;i++){pre=beg;beg=beg->next;}for(int i=1;i<n;i++){en=en->next;}cur=beg->next;beg->next=en->next;pre->next=en;pre=beg;while(pre!=en){tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}return res->next;// write code here}
};

第三个方法

/*** 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* head, int m, int n) {ListNode* res=new ListNode(0);//虚拟节点res->next=head;ListNode* pre=res;ListNode* cur=head;ListNode* beg=head;ListNode* tmp;for(int i=1;i<m;i++){pre=beg;beg=beg->next;}tmp=beg->next;for(int i=m+1;i<=n;i++){cur=tmp;tmp=tmp->next;beg->next=tmp;cur->next=pre->next;pre->next=cur;}return res->next;// write code here}
};

查看全文

http://www.lryc.cn/news/137167.html