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

设计一个原地反转链表的算法，可以使用迭代的方式，不需要额外的空间。基本思路是设置两个指针，一个指向当前节点，另一个称为“前驱”，它始终指向当前节点的前一个节点。然后，对于每个节点，我们首先将其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)，因为我们只使用了固定数量的变量，没有额外的数据结构。

相关问题

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

在C语言中，要原地逆转单向链表，可以使用迭代的方式。以下是简单的步骤：

1. 定义两个指针`prev`和`current`，初始时都指向头结点`head`（假设已存在）。

2. 开始一个循环，直到`current`为NULL（表示链表结束）：

a. 将`current`的下一个节点`next`保存到临时变量`temp`中。

b. 将`current`的`next`指针更新为`prev`。

c. `prev`和`current`分别向前移动一位，即`prev = current`, `current = temp`.

3. 循环结束后，`prev`会指向新的头结点，因为所有的节点已经被反转了链接。

下面是伪代码形式：

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    
    while (current != NULL) {
        Node* nextTemp = current->next; // 保存当前节点的下一个节点
        current->next = prev;        // 反转当前节点的指针
        prev = current;              // 移动prev指针
        current = nextTemp;          // 移动current指针
    }
    
    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作为新的头节点。