【C++】原地逆置单链表（不开辟新的储存空间）

首先看图例：

创建一个单链表L，并用指针p指向需要逆置的第一个结点，s指向p的下一个。（这里s的作用是为了防止p后的结点丢失）

第一个结点逆置后成为最后一个，所以其后为NULL，即p->next=NULL（其他结点正常头插）

用s指向了的p之后的结点，所以它们不会丢失。

第一个结点接上后，p、s重新指向之后需要逆置的结点。

第二个结点接上第一个，正常头插进去。p、s接着指。

重复上述过程，把最后一个结点也接上。

注意，当p为NULL时要break，不然下一个语句就是s=p->next，会程序出错。

逆置函数代码：

void inver(linklist &L)//头插法原地逆置
{
    int i=0;
    Lnode *p,*s;
    p=L->next;
    s=p->next;
    while(1)
    {
        if(i==0) {p->next=NULL;i++;}//第一个节点逆置后成为最后一个节点，之后应该是NULL
        else p->next=L->next;//其他正常头插
        L->next=p;
        p=s;
        if(p==NULL) break;//p==NULL，说明最后已逆置完成，赶紧退出循环，不然下一步“s=p->next”会报错
        s=p->next;
    }
}

完整代码：（输入数据为整型，以0为结束）

#include <bits/stdc++.h>//万能头文件

using namespace std;

typedef struct L
{
    int data;
    struct L *next;
}Lnode,*linklist;

void init_L(linklist &L)//初始化链表，‘&’一定要加！
{
    L=new Lnode;
    L->next=NULL;
}

void crep(linklist &L,int x)//头插法创建单链表，创建出来的链表是反序的，这里不用
{
    Lnode *p;
    p=(Lnode*)malloc(sizeof(Lnode));//为p开辟新的内存空间，如果不开可能会报错
    p->data=x;
    p->next=L->next;
    L->next=p;
}

void crea(linklist &L)//尾插法创建单链表
{
    int x;
    Lnode *p,*r;
    r=L;
    while(cin>>x)
    {
        if(x==0) break;
        p=(Lnode*)malloc(sizeof(Lnode));
        p->data=x;
        p->next=r->next;
        r->next=p;
        r=p;
    }
    p->next=NULL;
}

void inver(linklist &L)//头插法原地逆置
{
    int i=0;
    Lnode *p,*s;
    p=L->next;
    s=p->next;
    while(1)
    {
        if(i==0) {p->next=NULL;i++;}//第一个节点逆置后成为最后一个节点，之后应该是NULL
        else p->next=L->next;//其他正常头插
        L->next=p;
        p=s;
        if(p==NULL) break;//p==NULL，说明最后已逆置完成，赶紧退出循环，不然下一步“s=p->next”会报错
        s=p->next;
    }
}

void print(linklist &L)
{
    Lnode *p;
    p=L->next;
    while(p)
    {
        cout<<p->data<<' ';
        p=p->next;
    }
    cout<<endl;
}

int main()
{
    linklist L;
    init_L(L);
    crea(L);
    cout<<"原链表： ";
    print(L);
    inver(L);
    cout<<"逆置后的链表： ";
    print(L);
    return 0;
}

运行结果：