设计⼀个算法，将链表中所有结点的链接⽅向“原地”逆转，即要求仅利⽤原表的存储空间，换句话说，要求算法的空间复杂度为 O(1)。

设计一个原地反转链表的算法通常采用迭代的方式，不需要额外的数据结构。这里是一个步骤描述：

1. 定义三个指针：prev（前一个节点）、current（当前节点）和nextTemp（临时存储下一个节点的引用）。

2. 初始化 prev 和 current 分别指向 null 和头节点。

3. 当 current 不为空时，执行以下操作：
a. 将 current 的 next 指针暂时保存到 nextTemp 中。
b. 更新 current 的 next 指向 prev。
c. 将 prev 移动到 current。
d. 将 current 移动到 nextTemp （因为之前已经保存了下一个节点的位置）。

4. 当遍历完整个链表后，prev 就会成为新的头节点。

以下是 Python 代码实现示例：

def reverseList(head):
    prev = None
    current = head

    while current is not None:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp

    return prev  # 返回新头节点

相关问题

设计一个算法，将链表中所有结点的链接方向原地逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为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作为新的头节点。

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

算法步骤如下：

1. 定义三个指针，分别指向当前结点（cur）、当前结点的前一个结点（pre）和当前结点的后一个结点（next）。

2. 将当前结点的后一个结点保存在next中。

3. 将当前结点的next指向pre。

4. 将pre指向cur。

5. 将cur指向next。

6. 重复步骤2-5，直到cur指向尾结点为止。

7. 将头结点的next指向pre。

完整代码如下：

def reverse_linked_list(head):
    if not head or not head.next:
        return head
        
    pre = None
    cur = head
    while cur:
        next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    
    head.next = pre
    return head

时间复杂度为O(n)，空间复杂度为O(1)。