设计一个算法，利用单链表原来的结点空间逆转一个单链表

可以使用三个指针分别指向当前结点、前一个结点和后一个结点，然后依次遍历单链表，将当前结点的 next 指针指向前一个结点，然后将三个指针向后移动一个结点，直到遍历完整个单链表。最后将原来的头结点指向新的尾结点即可。

具体实现如下：

void reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next = nullptr;
    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head->next = prev;
}

其中，head 是原来的头结点，prev 是前一个结点，curr 是当前结点，next 是后一个结点。在遍历过程中，首先将 next 指针指向当前结点的下一个结点，然后将当前结点的 next 指针指向前一个结点，最后将 prev 和 curr 向后移动一个结点。遍历完整个单链表后，将原来的头结点指向新的尾结点 prev 即可。

相关问题

用C语言设计一个算法，利用单链表原来的结点空间逆转一个单链表

可以使用三个指针prev, current和next，分别指向当前节点的前一个节点、当前节点和下一个节点，然后依次遍历单链表，将每个节点的指针指向前一个节点，最后返回新的头节点即可。

以下是C语言的代码实现：

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

// 定义单链表节点
struct Node {
    int data;
    struct Node* next;
};

// 反转单链表
struct Node* reverseLinkedList(struct Node* head) {
    struct Node *prev, *current, *next;
    prev = NULL;
    current = head;
    while (current != NULL) {
        next = current->next; // 保存下一个节点
        current->next = prev; // 当前节点指向前一个节点
        prev = current; // 前一个节点更新为当前节点
        current = next; // 当前节点更新为下一个节点
    }
    return prev; // 新的头节点为原来的尾节点
}

// 打印单链表
void printLinkedList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    // 创建单链表
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = (struct Node*)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;

    // 打印原来的单链表
    printf("Original linked list: ");
    printLinkedList(head);

    // 反转单链表
    head = reverseLinkedList(head);

    // 打印反转后的单链表
    printf("Reversed linked list: ");
    printLinkedList(head);

    return 0;
}

运行结果：

Original linked list: 1 2 3 
Reversed linked list: 3 2 1 

设计一个算法，利用单链表原来的结点空间将一个单链表就地逆转

可以使用三个指针prev、curr、next，分别指向当前结点的前一个结点、当前结点和当前结点的后一个结点。遍历单链表，将当前结点的next指针指向prev，然后依次向后移动三个指针，直到遍历完整个单链表。最后将原来的头结点指向原来的尾结点，即可完成单链表的就地逆转。

具体实现如下：

void reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next = head->next;
    while (next != nullptr) {
        curr->next = prev;
        prev = curr;
        curr = next;
        next = next->next;
    }
    curr->next = prev;
    head->next = nullptr;
    head = curr;
}

其中，head为原来的头结点，prev、curr、next分别为三个指针，初始时prev为nullptr，curr为头结点，next为头结点的下一个结点。在遍历单链表的过程中，将当前结点的next指针指向prev，然后依次向后移动三个指针。最后将原来的头结点指向原来的尾结点，即curr，完成单链表的就地逆转。