带头结点和不带头结点的链表反转

### 带头节点与不带头节点单链表的反转算法 #### 不带头节点的单链表反转 对于不带头节点的单链表，可以通过迭代的方式实现反转。具体做法是维护三个指针变量 `prev`、`current` 和 `nextNode` 来完成操作。初始时，`prev` 设置为 `null`，表示反转后的最后一个节点指向空；`current` 初始化为原始链表的头部。 以下是具体的实现代码： ```java public class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; this.next = null; } } public static ListNode reverseList(ListNode head) { ListNode prev = null; // 初始前驱为空 ListNode current = head; // 当前节点初始化为头节点 while (current != null) { // 遍历整个列表 ListNode nextNode = current.next; // 保存当前节点的下一个节点 current.next = prev; // 将当前节点的下一节点指向前一节点 prev = current; // 更新前驱节点 current = nextNode; // 移动到下一个节点 } return prev; // 返回新的头节点 } ``` 此方法的时间复杂度为 O(n)，空间复杂度为 O(1)[^1]。 --- #### 带头节点的单链表反转 当存在头节点时，可以采用类似的逻辑来处理实际的数据节点部分。由于头节点本身并不存储有效数据，在反转过程中不需要改变其状态。通过遍历从第二个节点开始的实际数据节点并将其逐一插入到一个新的临时链表中即可完成反转。 下面是基于 Java 的实现代码： ```java public static void reverseWithHeadNode(ListNode dummyHead) { if (dummyHead == null || dummyHead.next == null || dummyHead.next.next == null) { return; // 如果链表为空或者只有一个节点，则无需反转 } ListNode prev = null; ListNode current = dummyHead.next; // 跳过虚拟头节点，直接访问第一个真实节点 while (current != null) { ListNode nextNode = current.next; // 记录后续节点 current.next = prev; // 修改当前节点的 next 指向之前的节点 prev = current; // 更新 previous 指针位置 current = nextNode; // 继续移动至下一位 } dummyHead.next = prev; // 完成后重新设置虚拟头节点的 next 字段为目标链表的新首部 } ``` 上述函数接受一个带有头节点的链表作为输入参数，并对其进行就地修改以达到反转效果[^2]。 --- #### 总结 无论是带还是不带头节点的情况，核心思想都是利用三重循环机制逐步调整各个节点之间的连接关系从而形成反序排列的结果。区别仅在于是否需要额外考虑头节点的存在与否及其特殊性质而已。