什么叫单链表就地逆置-排行榜大全

单链表的就地逆置指辅助空间的逆置方法。有普通循环和递归两种方法。

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指向我这个事实

什么叫单链表就地逆置