网站建设技术文章小程序搭建

编写一个算法来就地逆置一个单链表。默认情况下，链表是带头节点的，但如果链表不带头节点，逆置的过程会有所不同。

第一步：定义逆置函数

根据题目中的“试编写算法将单链表就地逆置”，我们需要：

1. 定义一个逆置函数 reverse，它接受一个链表头节点的引用作为参数。

这部分的代码为：

void reverse(LNode*& L) {LNode *p = L->next, *r;L->next = NULL;

第二步：逆置链表

根据题目中的“就地逆置”，我们需要：

1. 初始化 p 指向链表的第一个节点（跳过头节点）。
2. 使用 while 循环遍历链表，直到 p 为 NULL。
3. 在循环中，保存 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;}
}

代码过程

1. 初始化 p 指向第一个节点，L->next 为 NULL。
2. 在 while 循环中，r 保存 p 的下一个节点。
3. p->next 指向 L->next，即前一个逆置后的节点。
4. L->next 更新为 p，即当前逆置的节点。
5. p 移动到 r，即下一个待逆置的节点。
6. 重复步骤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。