单链表反转的图示操作

　　有一个线性表$(a_1,a_2, cdots, a_n)$, 采用带头结点的单链表$L$存储，设计一个算法将其就地逆置。所谓“就地”指辅助空间为$O(1)$。

解答：用$p$指针扫描原单链表，先将头结点$L$的$next$域置为$NULL$而变成一个空链表，然后，将$*p$结点采用头插法插入到$L$中。算法如下：

void Reverse(LinkList *&L){
    LinkList *p=L->next,*q;
    L->next=NULL;
    while (p!=NULL)
    {
        q=p->next;
        p->next=L->next; //将*p结点插入到新建链表的前面
        L->next=p;
        p=q;
    }

}

上述算法的图示操作如下：

//完整代码如下：

//LinkBase.h
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LinkList;

void InitList(LinkList *&L){
    L=(LinkList *)malloc(sizeof(LinkList));
    L->next=NULL;
}

void DestroyList(LinkList *&L){
    LinkList *p=L, *q=p->next;
    while(q!=NULL){
        free(p);
        p=q;
        q=p->next;
    }
    free(p);
    
}

int ListLength(LinkList *L){
    LinkList *p=L;
    int i=0;
    while(p->next!=NULL){
        i++;
        p=p->next;
    }
    return i;
}

void DispList(LinkList *L){
    LinkList *p=L->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("
");

}

int GetElem(LinkList *L,int i,ElemType &e){
    int j=0;
    LinkList *p=L;
    while(j<i && p!=NULL){
        j++;
        p=p->next;
    }

    if (p==NULL)
    {
        return 0;
    }
    else{
        e=p->data;
        return 1;
    }

}

int LocateElem(LinkList *L,ElemType e){
    LinkList *p=L->next;
    int n=1;
    while (p!=NULL && p->data!=e)
    {
        p=p->next;
        n++;
    }
    if(p==NULL)
        return 0;
    else
        return n;

}

int ListInsert(LinkList *&L,int i,ElemType e){
    int j=0;
    LinkList *p=L,*s;
    while (j<i-1 && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return 0;
    else{
        s=(LinkList *)malloc(sizeof(LinkList));
        s->data=e;
        s->next=p->next;
        p->next=s;
        return 1;
    }

}

int ListDelete(LinkList *&L,int i,ElemType &e){
    int j=0;
    LinkList *p=L,*q;
    while (j<i-1 && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return 0;
    else{
        q=p->next;
        if(q==NULL) return 0;
        e=q->data;
        p->next=q->next;
        free(q);
        return 1;

    }

}

//主函数.cpp
#include "LinkBase.h"
#include <stdio.h>

void Reverse(LinkList *&L){
    LinkList *p=L->next,*q;
    L->next=NULL;
    while (p!=NULL)
    {
        q=p->next;
        p->next=L->next; //将*p结点插入到新建链表的前面
        L->next=p;
        p=q;
    }

}


void main()
{
    LinkList *Ls = (LinkList *)malloc(sizeof(LinkList));
    Ls->next=NULL;
    int i=0;
    for (i=1;i<10;i++)
    {
        ListInsert(Ls,i,i*i-1);
    }

    printf("原线性表：
");
    DispList(Ls);

    //ListInsert(Ls,3,15);
    Reverse(Ls);
    printf("反转后的线性表：
");
    DispList(Ls);

    free(Ls);
}

效果如下：