单链表就地逆置算法：O(1)空间复杂度实现

本文介绍一种使用单链表作为存储结构，实现非空线性表的原地逆置算法。该算法的空间复杂度为O(1)，代码简洁易懂，适合学习数据结构与算法的初学者。

算法思路

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

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

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

代码实现

#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;
}

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

总结

本算法通过巧妙地利用指针操作，实现了单链表的原地逆置，算法的空间复杂度为O(1)，非常高效。

希望本文能够帮助你理解单链表就地逆置算法，并能将它应用到实际的编程问题中。