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

这个问题需要用到三个指针：p、q、r，p指向当前节点，q指向p的下一个节点，r指向q的下一个节点。每次将q的指针指向p，然后依次移动p、q、r指针，直到r指针为NULL为止。具体算法如下：

void reverseList(Node* head) {
    Node *p = head, *q = head->next, *r = q->next;
    p->next = NULL;
    while (r != NULL) {
        q->next = p;
        p = q;
        q = r;
        r = r->next;
    }
    q->next = p;
}

这样，链表中所有节点的链接方向就会被“原地”逆转，且空间复杂度为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作为新的头节点。