反转单链表的特定部分，即从m到n

Question

如何使此代码适用于m的所有值，即m=(1-10(中的任何值*此代码用于反转链表的特定部分。。此代码正在工作，但仅适用于m<5.当我们给出m的值为5或大于5时，它将进入一个无限循环。我不知道这个代码哪里出了问题。一个额外的帮助：-(，是否需要像我在析构函数中所做的那样使用delete((删除完整的链表：：因为我没有看到有人这样做，但我认为这是释放堆内存所必需的。*

#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next=NULL;
};
class LinkedList
{
Node *first=NULL,*last=NULL;
int no_of_nodes=10;
public:
LinkedList(int[],int);
~LinkedList();
void display(void);
void reverse(int m,int n);
};
LinkedList::~LinkedList()
{
Node *p=NULL;
for(int i=0;i<no_of_nodes;i++)
{
p=first;  
for(int j=0;j<no_of_nodes-i-1;j++)
{
if(p->next==last)
{
delete(p->next);
p->next=NULL;
last=p;
}
else
{
p=p->next;
}

}  
}
delete(first);
}
void LinkedList::reverse(int m,int n)
{
Node *prev=NULL,*pointer_m=first,*pointer_n=first;
//Making pointer_m to point on m-th node
for(int i=1;i<m;i++)
{
prev=pointer_m;
pointer_m=pointer_m->next;
}

//Making pointer_n to point on n-th node
pointer_n=first;               
for(int i=1;i<n;i++)
{
pointer_n=pointer_n->next;
}
// reversing the list part between m and n
Node *p=first->next,*q=first,*r=prev;      // q and r are tailing pointers

while(q!= pointer_n  && p)
{
r=q;
q=p;
p=p->next;
q->next=r;
}
//fixing pointers
prev->next=pointer_n;
pointer_m->next=p;
}
LinkedList::LinkedList(int arr[],int n)
{
first=new Node;
first->data=arr[0];
last=first;
for(int i=1;i<n;i++)
{
Node *temp=new Node;
temp->data=arr[i];
last->next=temp;
last=temp;
}
}

void LinkedList::display(void)
{
Node *p=first;
//  cout<<"No.of nodes:: "<<no_of_nodes<<"tt";
cout<<"List is:: ";
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main(void)
{
int arr[]={2,4,6,8,10,12,14,16,18,20};
int n=sizeof(arr)/sizeof(arr[0]);
LinkedList list(arr,n);
list.display();
list.reverse(5,8);
list.display();
return 0;
}

Answer 1

主要错误源于三个回归变量`p，q，r`的初始值设置错误。3节点正在运行反向段"(m->n("，以向后设置节点的链接。三个应该从"m"开始，而不是从开头开始。

// Reversing a specific part of singly Linked List i.e from m=3 to n=7
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next=NULL;
};
class LinkedList
{
Node *first=NULL,*last=NULL;
int no_of_nodes=10;
public:
LinkedList(int[],int);
~LinkedList();
void display(void);
void reverse(int m,int n);
};
LinkedList::~LinkedList()
{
Node *p=NULL;
for(int i=0;i<no_of_nodes;i++)
{
p=first;
for(int j=0;j<no_of_nodes-i-1;j++)
{
if(p->next==last)
{
delete &(p->next->data);
p->next=NULL;
last=p;
break;
}
else
{
p = p->next;
}
}
}
delete &(first->data);
first = NULL;
}
void LinkedList::reverse(int m,int n)
{
Node *prev_m, *pointer_m, *pointer_n;
if (n >= no_of_nodes) n = no_of_nodes - 1;
//Making pointer_m to point on m-th node
prev_m = first;
for(int i=1;i<m;i++) prev_m = prev_m->next;
pointer_m = prev_m->next;
//Making pointer_n to point on n-th node
pointer_n=first;
for(int i=0;i<n;i++) pointer_n = pointer_n->next;
//  reversing the list part between m and n
Node *p, *q, *r;
r = pointer_m;
q = r->next;
p = q->next;      // q and r are tailing pointers
q->next = r;
while(q!= pointer_n  && p != last)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
//fixing pointers
if(m!=1)
{
prev->next=pointer_n;
pointer_m->next=p;
}
else
{
first=pointer_n;
pointer_m->next=p;
}
}

LinkedList::LinkedList(int arr[],int n)
{
Node *temp;
first = new Node;
first->data = arr[0];
last = first;
for(int i=1 ;i<n; i++)
{
temp = new Node;
temp->data = arr[i];
last->next = temp;
last = temp;
}
no_of_nodes = n;
}

void LinkedList::display(void)
{
Node *p; p = first;
cout<<"List is:: ";
while(p != last)
{
cout<< (p->data) <<" ";
p = p->next;
}
cout<< last->data << endl;
}
int main(void)
{
int arr[]={2,4,6,8,10,12,14,16,18,20};
int n=sizeof(arr)/sizeof(arr[0]);
LinkedList list(arr,n);
list.display();
list.reverse(3,7);
list.display();
return 0;
}

测试运行会将节点从3反转为7。

$ ./a.exe
List is:: 2 4 6 8 10 12 14 16 18 20
List is:: 2 4 6 16 14 12 10 8 18 20