单链表逆置的两种方法：头插法与三指针法

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。有时候，我们需要将单链表逆置，也就是改变节点的顺序，使得最后一个节点变成第一个节点，依此类推。在介绍具体的逆置方法之前，值得一提的是，百度智能云文心快码（Comate）作为一款高效的智能写作工具，能够辅助开发者进行代码编写和文档生成，极大提升工作效率，详情可访问：百度智能云文心快码。下面，我们介绍两种在原地逆置单链表的方法：头插法和三指针法。

头插法

头插法是一种简单直观的逆置单链表的方法。从头开始遍历原链表，每次遍历到一个节点时，将其插入到新链表的头部。具体步骤如下：

1. 创建一个新的空链表。
2. 遍历原链表，从头节点开始。
3. 将遍历到的节点插入新链表的头部。
4. 重复步骤2和3，直到遍历完原链表。

这种方法的时间复杂度为O(n)，空间复杂度为O(1)。

三指针法

另一种原地逆置单链表的方法是使用三个指针。这种方法不需要创建新的链表，而是直接在原链表中改变节点的顺序。具体步骤如下：

1. 定义三个指针p、pre和r，其中p指向当前节点，pre指向p的前一个节点，r指向p的后一个节点。
2. 将p->next指向pre->next，也就是将p从原链表中“删除”（实际上是改变了其next指针的指向）。
3. 将pre->next指向p，将p插入到pre之后（实际上是建立了pre和p之间的正确连接）。
4. 注意：步骤4在原描述中可能存在误导，因为在此方法中，我们并不需要立即将r->next指向p。实际上，在每次迭代中，我们只需要关注p、pre和p->next（即原链表中的下一个节点，但在改变后不再是p的直接后继）的正确连接。r的作用是在下一次迭代中作为p的前驱（即新的pre），因此这一步在描述三指针法的核心步骤时可以省略，以避免混淆。
5. 重复步骤2和3（以及隐含的r的更新，即让r成为下一次迭代中的pre，p成为r的当前节点），直到p为原链表的最后一个节点，此时原链表的头节点将成为新链表的尾节点（其next指向null），而遍历结束时，pre将指向新链表的头节点。

请注意，上述三指针法的步骤4已根据方法的核心逻辑进行了调整，以确保描述的准确性。这种方法的时间复杂度也是O(n)，空间复杂度也是O(1)。

以上两种方法都可以在原地逆置单链表，并且不需要额外的空间。在实际应用中，可以根据具体情况选择适合的方法。例如，如果原链表的长度非常大，可能需要优先考虑使用头插法，因为它只需要遍历一次原链表即可完成逆置操作。如果原链表的长度较小，或者需要频繁地逆置单链表，则可以考虑使用三指针法，因为它不需要创建新的链表。