设计一个算法将链表中所有节点的逆序，要求利用原表的存储空间

设计一个算法将链表中所有节点的顺序逆转，而不创建新的存储空间，可以使用迭代或递归的方式来实现，这里我们给出一种常用的迭代方法：

**迭代法：**

1. 初始化三个指针，当前节点 `current`、前一个节点 `prev` 和下一个节点 `next`，都设置为链表的头结点。

2. 遍历链表，直到遇到末尾的 `None` 或空节点：
- 将 `current` 的下一个节点赋值给 `next`。
- 将 `current` 指向 `prev`。
- 将 `prev` 更新为 `current`（即 `prev` 向后移动一位）。
- 如果 `next` 不为空，则继续遍历；否则结束循环。

3. 当遍历结束后，链表的头结点会变成原来的尾部，而尾部变成了原来的头部。所以，`prev` 现在指向的就是反转后的链表的头结点。

def reverse_list(head):
    prev = None
    current = head
    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev  # 返回新的头结点

相关问题

设有一个表头指针为L的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。

为了实现这个功能，我们可以采用迭代的方式遍历链表，并在遍历过程中调整节点之间的引用。这里是一个简单的步骤描述：

1. 初始化两个指针，分别命名为 `prev` 和 `current`，初始都设置为 `NULL`。`prev` 用于存储当前节点的前一个节点，而 `current` 则指向当前正在处理的节点，即链表头部的 `L`。

2. 当 `current` 不为 `NULL` 时，执行以下操作：
a. 将 `current` 的下一个节点赋值给临时变量 `next`，保存当前节点的后继节点。
b. 将 `current` 的指向前驱设为 `prev`，使其反转链接。
c. 更新 `prev` 指向 `next`，即将 `prev` 移动到下一个位置。
d. 将 `current` 赋值为 `next`，继续处理下一位节点。

3. 遍历结束后，`current` 就会变成 `NULL`，此时 `prev` 就是指向原链表尾部的节点，它之前的所有节点已经被逆序连接。所以，只需将 `prev` 指向的节点设置为新的链表头 `L`，就可以完成整个链表的逆序。

以下是伪代码形式的算法：

L = 单链表头
prev = NULL
current = L

while current != NULL:
    next = current.next
    current.next = prev  # 反转当前节点的指向
    prev = current       # 更新前驱节点
    current = next       # 继续遍历

if prev != NULL:  # 如果不是空链表
    L = prev  # 新的头节点是之前的尾节点

链表的逆序打印Java递归算法

可以使用递归算法来实现链表的逆序打印，具体实现如下：

public void printListReversingly(ListNode head) {
    if (head != null) {
        if (head.next != null) {
            printListReversingly(head.next);
        }
        System.out.print(head.val + " ");
    }
}

其中，ListNode 是链表节点的定义，val 表示节点的值，next 表示指向下一个节点的指针。该算法的思路是先递归到链表的最后一个节点，然后从后往前依次打印节点的值。

注意，该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 表示链表的长度。