设计一个算法，将链表中所有节点的链接方向“原地”逆转，即要求仅利用原表的存储结构，换句话说，要求算法的空间复杂度为O（1）

设计一个原地逆转链表的算法可以采用迭代法，不需要额外的空间。以下是Python的伪代码实现：

def reverseList(head):
    prev = None  # 初始化前驱节点为None
    curr = head  # 当前节点指向头节点

    while curr is not None:  # 当当前节点不为空时
        next_node = curr.next  # 获取当前节点的下一个节点
        curr.next = prev  # 将当前节点的next指向前驱节点
        prev = curr       # 更新前驱节点为当前节点
        curr = next_node   # 更新当前节点为下一个节点

    return prev  # 返回新的头节点，因为最后一个节点的next已经设为None，所以prev就是反转后的头

这个算法通过三个指针（prev、curr和next_node）来改变节点之间的链接，每次迭代都将当前节点的next指向前一个节点，然后移动指针向前。由于整个过程都在链表本身上操作，空间复杂度确实是O(1)。

相关问题

设计一个算法，将链表中所有节点方向原地逆转，要求仅利用原表的存储空间 换句话说，要求算法的空间复杂度为

设计一个原地反转链表的算法，可以使用迭代的方式，不需要额外的空间。基本思路是设置两个指针，一个指向当前节点，另一个称为“前驱”，它始终指向当前节点的前一个节点。然后，对于每个节点，我们首先将其next指针指向前驱节点，再将前驱节点和当前节点向后移动一步。直到遍历到链表的末尾，此时前驱节点就是新的头节点。

伪代码如下：

function reverseList(head):
    if head is None or head.next is None:
        return head

    prev = None     # 初始化前驱指针
    curr = head     # 初始化当前指针

    while curr is not None:
        next_temp = curr.next   # 保存当前节点的下一个节点
        curr.next = prev        # 将当前节点的next指向前驱
        prev = curr              # 更新前驱为当前节点
        curr = next_temp         # 移动当前节点到下一个位置

    return prev  # 返回新头节点

这个算法的时间复杂度是O(n)，其中n是链表的长度，因为需要遍历整个链表一次。空间复杂度是O(1)，因为我们只使用了固定数量的变量，没有额外的数据结构。

设计一个算法，将链表中所有结点的链接方向原地逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为1

设计一个原地逆转链表的算法可以使用迭代的方式，这里是一个Python的例子：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head
    while curr is not None:
        # 将当前节点的next指向前一个节点
        next_temp = curr.next
        curr.next = prev
        # 更新prev和curr，向后移动一位
        prev = curr
        curr = next_temp
    return prev  # 返回新的头节点，原头节点变成了最后一个节点

这个算法的基本思路是通过三个指针（prev、curr和next_temp），每次迭代都将curr节点的next指向前一个节点prev，然后更新这三个指针的位置，直到遍历完整个链表。最后返回prev作为新的头节点。