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

为了原地反转一个链表，你可以使用迭代或者递归的方式来实现。这里给出一种迭代的方法：

**迭代法（两指针法）：**

1. 定义两个指针，分别称为 `prev` 和 `curr`，初始时都指向链表的头节点 `head`，`prev` 为空。

2. 当 `curr` 不为 null 时，进入循环：
- 将 `curr` 的下一个节点赋值给临时变量 `next`，保存当前节点的下一个节点。
- 更新 `curr` 的下一个节点为 `prev`，即将当前节点的链接转向它的前一个节点。
- 移动 `prev` 和 `curr` 向后一位，即 `prev = curr` 和 `curr = next`。

3. 循环结束后，`prev` 就会成为新的头节点，因为最后一次迭代时 `curr` 指向了 null，所以 `prev` 的下一个节点就是空（null），实现了链表的反转。

Python伪代码示例：

def reverseList(head):
    prev = None
    curr = head
    
    while curr is not None:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
        
    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作为新的头节点。

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

设计一个原地逆转链表的算法，可以使用迭代法，不需要额外的空间。这里是一个简单的C语言实现：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
struct ListNode {
    int val;       // 节点值
    struct ListNode* next;  // 指向下一个节点的指针
};

// 用于原地反转链表的函数
void reverseList(struct ListNode** head) {
    if (*head == NULL || (*head)->next == NULL) {  // 如果链表为空或只有一个节点，直接返回
        return;
    }
    
    struct ListNode* prev = NULL;  // 初始化前驱节点
    struct ListNode* current = *head;  // 当前节点指向头节点

    while (current != NULL) {  // 遍历链表
        struct ListNode* nextTemp = current->next;  // 保存当前节点的下一个节点
        current->next = prev;  // 将当前节点的next指向前一个节点
        prev = current;  // 更新前驱节点
        current = nextTemp;  // 移动到下一个节点
    }

    *head = prev;  // 最后，头节点变为原来的尾节点
}

// 测试函数
int main() {
    // 创建一个测试链表
    struct ListNode* list = malloc(sizeof(struct ListNode));
    list->val = 1;
    list->next = malloc(sizeof(struct ListNode));
    list->next->val = 2;
    list->next->next = malloc(sizeof(struct ListNode));
    list->next->next->val = 3;

    printf("Original List: ");
    struct ListNode* temp = list;
    while (temp != NULL) {
        printf("%d -> ", temp->val);
        temp = temp->next;
    }
    printf("NULL\n");

    reverseList(&list);  // 反转链表

    printf("Reversed List: ");
    temp = list;
    while (temp != NULL) {
        printf("%d -> ", temp->val);
        temp = temp->next;
    }
    printf("NULL\n");

    free(temp);  // 释放内存
    return 0;
}

在这个例子中，`reverseList` 函数通过改变每个节点的 `next` 指针，实现了链表的原地逆转。注意，在实际应用中，你需要确保在遍历过程中不会引起数据丢失。