编写一个算法来就地逆置一个单链表。默认情况下，链表是带头节点的，但如果链表不带头节点，逆置的过程会有所不同。
第一步：定义逆置函数
根据题目中的“试编写算法将单链表就地逆置”，我们需要：
- 定义一个逆置函数
reverse，它接受一个链表头节点的引用作为参数。
这部分的代码为：
void reverse(LNode*& L) {LNode *p = L->next, *r;L->next = NULL;
第二步：逆置链表
根据题目中的“就地逆置”，我们需要：
- 初始化
p指向链表的第一个节点（跳过头节点）。 - 使用
while循环遍历链表，直到p为NULL。 - 在循环中，保存
p的下一个节点到r，然后将p的next指向头节点的下一个节点，最后更新头节点的next为p。
这部分的代码为：
while (p != NULL) {r = p->next; // 保存下一个节点p->next = L->next; // 逆置当前节点L->next = p; // 更新头节点的nextp = r; // 移动到下一个节点}
}
第三步：处理不带头节点的链表
如果链表不带头节点，我们需要稍微修改上述代码。在这种情况下，我们不需要头节点，可以直接操作原链表的头节点。
这部分的代码为：
void reverseNoHead(LNode*& L) {LNode *p = L, *r;L = NULL; // 新的头节点初始化为NULLwhile (p != NULL) {r = p->next; // 保存下一个节点p->next = L; // 逆置当前节点L = p; // 更新新的头节点p = r; // 移动到下一个节点}
}
完整代码
// 带头节点的逆置
void reverse(LNode*& L) {LNode *p = L->next, *r;L->next = NULL;while (p != NULL) {r = p->next;p->next = L->next;L->next = p;p = r;}
}// 不带头节点的逆置
void reverseNoHead(LNode*& L) {LNode *p = L, *r;L = NULL;while (p != NULL) {r = p->next;p->next = L;L = p;p = r;}
}
代码过程
- 初始化
p指向第一个节点，L->next为NULL。 - 在
while循环中，r保存p的下一个节点。 p->next指向L->next，即前一个逆置后的节点。L->next更新为p，即当前逆置的节点。p移动到r，即下一个待逆置的节点。- 重复步骤2-5，直到
p为NULL。
假设我们有一个单链表：1 -> 2 -> 3 -> 4，我们将通过表格来展示每一步的变化。
| 步骤 | L->next | p | r | p->next | L->next 更新 | p 更新 |
|---|---|---|---|---|---|---|
| 初始 | 2 | 2 | NULL | 3 | NULL | 3 |
| 1 | NULL | 2 | 3 | 4 | 3 | 3 |
| 2 | 3 | 3 | 4 | NULL | 2 | 4 |
| 3 | 2 | 4 | NULL | NULL | 1 | NULL |
在逆置过程中，我们首先将头节点的 next 指针设置为 NULL，然后遍历链表，每次将当前节点的 next 指针指向前一个逆置后的节点，然后将头节点的 next 指针更新为当前节点，最后将当前节点更新为其下一个节点。
最终，链表将被逆置为：4 -> 3 -> 2 -> 1。
