线性表算法设计题（七）

题目

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

算法思想

此题的关键点在于不能开辟新的空间，只能改变指针的方向。因此，可以考虑逐个摘取结点，利用前插法创建链表的思想，将结点依次插到头结点的后面。因为先插入的结点为表尾，后插入的结点为表头，即可实现链表的逆转。

完整代码

#include <iostream>
using namespace std;

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

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode, *LinkList;

//创建链表
int CreateList(LinkList &L,int n){
    LNode *p,*r;
    int i;
    L = new LNode;
    L -> next = NULL;
    r = L;
    for(i = 0;i < n;i ++)
    {
        p = new LNode;
        cin >> p -> data;
        p -> next = NULL;
        r -> next = p;
        r = p;
    }
    return 0;
}

void Inverse(LinkList &L){
    //逆置带头结点的单链表L 
    LinkList p, q;
    p = L -> next;              //p指向首元结点 
    L -> next = NULL;           //头结点的指针域置为空 
    while(p != NULL){           //遍历链表，如果下一个结点存在 
        q = p -> next;          //q指向*p的后继 
        p -> next = L -> next;
        L -> next = p;          //*p插入在头结点之后 
        p = q;
    }
} 

//输出链表
void display(LinkList L){
    LNode *p;
    p = L-> next;
    cout << "(";
    while(p){
    cout << p -> data << " ";
    p = p -> next;
    }
    cout << ")" << endl;
}

int main(){
    LinkList L;
    int n;
    cout << "请输入链表的长度：";
    cin >> n;
    cout << "请依次输入要存入的数据：" << endl;
    CreateList(L, n);
    cout << "链表如下：" << endl;
    display(L);
    Inverse(L);
    cout << "逆置后的链表如下：" << endl;
    display(L); 
    return 0;
}

结果显示

TIM图片20191026125429.png