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

可以使用三个指针来完成该算法，分别指向当前遍历的结点、其前驱结点和其后继结点。具体步骤如下：

1. 初始化三个指针pre、cur、next，分别指向头结点的前驱结点、头结点和头结点的后继结点。
2. 遍历链表，依次将cur的next指向pre，然后将pre、cur、next指针依次向后移动一个结点，直到遍历到链表的末尾。
3. 将头结点的next指向pre，完成链表的反转。

以下是具体的代码实现：

void reverseList(ListNode* head) {
    if(head == NULL || head->next == NULL) {
        return;
    }
    ListNode* pre = NULL;
    ListNode* cur = head;
    ListNode* next = head->next;
    while(next != NULL) {
        cur->next = pre;
        pre = cur;
        cur = next;
        next = next->next;
    }
    cur->next = pre;
    head->next = cur;
}

需要注意的是，该算法的时间复杂度为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作为新的头节点。

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

可以采用迭代的方式来原地逆转链表，具体实现如下：

1. 定义三个指针，分别为prev、curr、next，分别指向前一个结点、当前结点和下一个结点。

2. 初始化prev为NULL，curr为链表的头结点。

3. 遍历链表，直到curr为NULL。在遍历过程中，执行以下步骤：

a. 将next指针指向curr结点的下一个结点。

b. 将curr结点的next指针指向prev结点。

c. 将prev指针指向当前结点curr。

d. 将curr指针指向next。

4. 返回prev作为新的头结点。

代码实现如下：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head, *next;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}