以单链表作存储结构存储非空线性表编写一个实现线性表就地逆置的算法。空间复杂度均是O1。#include iostreamusing namespace std;typedef int DataType;typedef struct node DataType data; node next;node;node first;int length;vo

首先，将链表分成两部分，一部分是已经逆置的部分，一部分是未逆置的部分。初始化时已经将链表存储完毕，首节点first不需要逆置。

然后，从第二个节点开始，依次将每个节点插入到已逆置部分的首节点之前，直到最后一个节点。

最后，将首节点指向最后一个节点，链表逆置完成。

具体代码如下：

void reverseList()
{
    if (length <= 1) { // 如果链表长度小于等于1，不需要逆置
        return;
    }
    
    node* p = first->next; // 第一个节点
    node* q = p->next; // 第二个节点
    
    while (q != NULL) {
        node* r = q->next; // 保存下一个节点
        
        q->next = p; // 将当前节点指向前一个节点
        
        p = q; // 更新前一个节点为当前节点
        q = r; // 更新当前节点为下一个节点
    }
    
    first->next->next = NULL; // 第一个节点指向NULL
    first->next = p; // 首节点指向最后一个节点
}

在主函数中调用reverseList函数即可实现链表的就地逆置。

完整代码如下：

#include <iostream>
using namespace std;

typedef int DataType;
typedef struct node {
    DataType data;
    node* next;
} node;
node* first;
int length;

void init()
{
    first = new node;
    first->next = NULL;
    node* rear = first;
    cin >> length;
    for (int i = 0; i < length; ++i) {
        DataType elem;
        cin >> elem;
        node* s = new node;
        s->data = elem;
        s->next = NULL;
        rear->next = s;
        rear = s;
    }
}

void reverseList()
{
    if (length <= 1) { // 如果链表长度小于等于1，不需要逆置
        return;
    }
    
    node* p = first->next; // 第一个节点
    node* q = p->next; // 第二个节点
    
    while (q != NULL) {
        node* r = q->next; // 保存下一个节点
        
        q->next = p; // 将当前节点指向前一个节点
        
        p = q; // 更新前一个节点为当前节点
        q = r; // 更新当前节点为下一个节点
    }
    
    first->next->next = NULL; // 第一个节点指向NULL
    first->next = p; // 首节点指向最后一个节点
}

void show()
{
    node* p = first->next;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main()
{
    init();
    reverseList();
    show();
    return 0;
}

这样就实现了使用单链表作为存储结构存储非空线性表，并且可以就地逆置线性表的算法。算法的空间复杂度是O(1)。