单链表的就地逆置指辅助空间的逆置方法。有普通循环和递归两种方法。
1、普通循环法：普通循环法是逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头，即“头插”到逆置链表中，使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。
2、递归：递归是先假定有一个函数，可以将以head为头结点的单链表逆序，并返回新的头结点。将链表分为当前表头结点和其余部分，递归的过程就是，先将表头结点从链表中拆出来，然后对其余部分进行逆序，最后将当前的表头结点链接到逆
什么叫“单链表就地逆置”？
比如说链表
a -> b -> c -> d
表头是a，表尾是d。就地逆置的意思就是变成：
a <- b <- c <- d
a变成表尾，d变成表头
假设
struct LINK {
int value;
struct LINK * next;
};
struct LINK a, b, c, d;
a->next = &b;
b->next = &c;
c->next = &d;
d->next = 0;
逆置后：
b->next = &a;
c->next = &b;
d->next = &c;
a->next = 0;
所谓就地逆置，就是在操作中，遇到a->next = &b;的情况，那么改写为b->next = &a;
单链表就地逆置的两种方法(递归与普通循环)
一、用递归算法
对于不带头结点的单链表（a1,a2,a3,a4,a5,a6）逆置后的结果为（a6,a5,a4,a3,a2,a1）
考虑递归算法，若只有一个结点，则直接返回，若存在两个结点（a1,a2）则需要做的操作有：
a2->next=a1;a1->next=NULL;return a2;
a2即新的头结点，若有三个结点,则应先将子链（a2,a3）先逆置且返回该子链的新的头结点，然后把子链（a2,a3）当作一个复合结点a2'，组成新的二元组（a1,a2'）然后就可以执行前面相同的操作：a2'->next=a1;a1->next=NULL;return a3'; 即可，多个以上的结点可同理得到，
Node *Reverse(Node *head)
{
Node *p=head;
if(p==NULL)
return NULL; //若是空链表，返回空
Node *q=p->next;
if(q==NULL)
return p; //若只有一个结点，直接返回
else
head=Reverse(q);//记录子序列的新的头结点
q->next=p; //当前结点与已经逆置的子序列看成是前后的两个结点p,q，作相应的逆置操作
p->next=NULL;
return head; //返回新的子序列的头结点
}
二、用普通算法循环逆置（头插法重新建立带头结点的新链表）
参考链接：https://blog.csdn.net/onlyoncelove/article/details/81988514
单链表的就地逆置的算法！！
就地逆置即算法的辅助空间为O(1)。
思路为：逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。
实现代码：
void converse(LinkList *head){
LinkList *p,*q;
p=head->next;
head->next=NULL;
while(p)
{
/*向后挪动一个位置*/
q=p;
p=p->next;
/*头插*/
q->next=head->next;
head->next=q;
}
}
链表就地逆置p->next=head->next意思
注意head每次指向哪个节点
head->next总是指向已经经过逆置的最后一个节点，也就是新的经过逆置的头节点
所以每次完成一个新的节点的逆置，要将其next指向上一个逆置的节点，刚好是head->next指向的节点
比如原来有链表 A->B->C->D->NULL
开始head->next = A, head->next->next=B
首先让p=A,并让A->next=NULL, 也就是让A成为尾节点
然后q指向B，此时head->next还是指向A的，也就是刚刚完成逆置的节点
while开始之后
每次都将q赋值给p，于是 p=B, q =C, B->next=head->next = A, head-next = B
此时head->next指向B，刚好又是刚完成逆置的节点
以后继续循环
试写一算法对单链表实现就地逆置？
void Inverse(LinkList &L)
{
LNode *p, *q;
p = L->next; /*记录第一个结点地址*/
L->next = NULL; /*把链表设置成空表*/
while (p != NULL) /*依次按头插法将各结点插入，就实现了逆置*/
{
q = p; /*用q记录待插入结点地址*/
p = p->next; /*用p记录待插入结点的后继结点地址*/*/
q->next = L->next; /*将q（待插入结点）插入到头结点的前面*/
L->next = q; /*将新插入结点作为新的头*/
}
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
对单链表实行就地逆置算法?
其实就是建立链表有的头插法
#define ElemType char
typedef struct Node{
ElemType data;
struct Node *next;
}Node,*LinkList;
void ReverseList(LinkList L)
{
Node *p,*q;
p = L->next; /*p为原链表的当前处理节点*/
L->next = NULL; /*逆置单链表初始为空*/
while(p != NULL){ /*当原链表未处理完*/
q = p->next; /*q指针保留原链表当前处理节点的下一个节点*/
p->next = L->next; /*将当前处理节点p插入到逆置L的表头*/
L->next = p;
p = q; /*p指向下一个待插入的节点*/
}
}
单链表逆置问题！不是就地逆置是将逆置的结果存放于另一单链表中 但是原单链表不变！
struct N
{
T data; // 这个的类型根据需要改
N *next;
};
N* revert(N* l)
{
N *ret = NULL;
while (l != NULL)
{
N *newnode = new N;
newnode->data = l->data;
newnode->next = ret;
ret = newnode;
l = l->next;
}
return ret;
}
关于单链表的所有结点逆置
//就地逆置单链表
//定义结点数据元素结构体
typedef struct snode
{
DataType x;
struct snode *next;
}SLNode;
//逆置算法
void ListReverse(SLNode *head)
{
int i=-1,j;
DataType x;
SLNode *p,*q;
p=head;
while(p->next!=NULL&&i<(ListLength(head)-1)/2)
{
p=p->next;
i++;
q=head;
j=-1;
while(q->next!=NULL&&j<ListLength(head)-1-i)
{
q=q->next;
j++;
}
x=p->data;
p->data=q->data;
q->data=x;
}
}
已知带头结点的单链表L,编写算法删除L中国从k开始的n个元素,并将得到的链表就地逆置
bool Del_k_n(LinkList &linkList,int k,int n){
LNode *pre=linkList->next,*r,*p=linkList;
while (pre!=NULL&&(--k)!=0){//查找开始结点
p=pre;
pre=pre->next;
}
if (pre==NULL) return false;//开始结点为空，删除失败
r=pre;
while (r!=NULL&&(--n)!=0){//查找结束结点
r=r->next;
}
p->next=r->next;
while (pre!=p->next){//删除元素
r=p->next;
free(pre);
pre=r;
}
p=linkList->next;
linkList->next=NULL;
while (p){//逆置
r=p->next;
p->next=linkList->next;
linkList->next=p;
p=r;
}
return true;
}
试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓"就地"指辅助
——while(q)是指q指的内容不为空的情况下吗？
没错。
——可是之前的语句已经使它为空了呀？？
这个不对。
之前对q的赋值就只有这句：q=p->next
并没有把NULL赋值给他
如果你觉得这两句语句q=p->next;
p
->
next=NULL;
具有传递性，于是就等价于q
=
NULL
的话，你需要对指针这个东西有更深入的理解
q=p->next;
是让q只想p的next指针所指的东西，比如q->next本来指向我这个人，那么现在q也指向我了。q->next也指向我，不变。
p
->
next=NULL;
的意思是让p->next
指向空。但是这不影响刚才执行以后
q指向我这个事实
相关推荐：
