数据结构作业——P53页算法设计题（7）：原地逆转链表

程序员永龙技术 2022年11月18日

0 收藏 807 点赞 2,943 浏览 1049 个字

一、题目描述：

设计一个算法，将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为O(1)。

二、算法设计

#include<iostream>using namespace std;/*
*课本p53 页第七题
*
*/
#define ElemType inttypedef struct LNode{
    ElemType data;   //定义数据域
    struct LNode *next;
}LNode,*LinkList;void CreateList(LinkList &L){
    L = new LNode;      //申请存储空间
    L->next = NULL;    int n;
    cout<<"请输入单链表长度："<<endl;
    cin>>n;
    LinkList r =L;
    cout<<"请输入单链表的数据元素："<<endl;
    for(int i=0;i<n;i++){
        LinkList p = new LNode;
        cin>>p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}void Display(LinkList &L){
    LinkList p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}void TurnList(LinkList &L){   //逆转链接结点
    LinkList p,q,r;
p=L->next;//记录list下一个结点的指针
q=L->next->next;//记录list下下一个结点的指针
r=L->next->next->next;//记录list下下下一个结点的指针
while(r)
{
q->next=p;//将一个结点的指针赋给下一个结点的指针域
p=q;
q=r;
r=r->next;//指针p,q,r整体往右移一位
}
r=q;//记录最后一位元素的指针
q->next=p;//将倒数第二个元素的指针赋给最后一位元素的指针域
L->next->next=NULL;//将第一个元素的指针域设为NULL
L->next=r;//将最后一个元素的指针赋给原本头结点指针的指针域
Display(L);
}int main(){
    cout<<"P53页第7题："<<endl;
    cout<<endl;
    LinkList L;
    CreateList(L);
    cout<<"新创建好的单链表为："<<endl;
    Display(L);
    cout<<"逆转后的新表为："<<endl;
    TurnList(L);
}