设有一个表头指针为L的无头结点的非空单链表。设计一个算法，将链表中所有结点的链接方向逆转，即要求仅利用原表的存储空间（也就是说，算法的空间复杂度为O(1)）。
思路
用到了三个指针变量p1、p2、p3，分别对应当前节点、当前节点的前一个节点和下一个节点。
首先，检查链表L是否为空或者只有一个节点，如果满足这些条件，那么链表已经是反转的，直接返回即可。
然后，初始化p1和p2，p1指向链表的第二个节点，p2指向链表的第一个节点。这里的目标是将p2的next指针指向p1，即反转链表的链接方向。
接下来，进入一个循环，直到p1为空（也就是链表的末尾）。在每次循环中，首先将p3设置为p1，然后将p1向后移动一位（即p1 = p1->next）。然后，将p3的next指针指向p2，这就完成了一个节点链接方向的反转。然后，将p2设置为p3，为下一次循环做准备。
循环结束后，所有的节点链接方向都已经反转，但是链表头指针L还指向原链表的第一个节点，所以最后将L设置为p3，即新链表的第一个节点。
这个过程只需要遍历一次链表，时间复杂度是O(n)，并且只使用了三个额外的指针变量，空间复杂度是O(1)。
代码
#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using Status = int;
using ElemType = int;const int N = 1e6 + 7;
const int TRUE = 1;
const int FALSE = 0;
const int OK = 1;
const int ERROR = 0;
const int INFEASIBLE = -1;
const int OVERFLOW = -2;int n;
ElemType a[N];struct ListNode {ElemType data;ListNode *next;
};
using LinkedList = ListNode *;Status initList(LinkedList &first) {first = NULL;return OK;
}Status listInsert(LinkedList &L, int pos, ElemType e) {ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));newNode->data = e;if (!pos) {newNode->next = L;L = newNode;return OK;}ListNode *p = L;for (int i = 0; p && i < pos - 1; i++) {p = p->next;}newNode->next = p->next;p->next = newNode;return OK;
}ElemType getElem(LinkedList L, int pos) {ListNode *p = L;for (int i = 0; p && i < pos; i++) {p = p->next;}return p->data;
}Status reverse(LinkedList &L) {if (!L || !L->next) {return OK;}ListNode *p1, *p2, *p3;p1 = L->next;p2 = L;while (p1) {p3 = p1;p1 = p1->next;p3->next = p2;p2 = p3;}L = p3;return OK;
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}LinkedList L;initList(L);for (int i = 0; i < n; i++) {listInsert(L, i, a[i]);}for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";reverse(L);for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";return 0;
}