链表原地反转（链表)

链表的原地反转是一种常见的链表操作，它可以通过改变链表节点之间的指针来实现链表的反转。原地反转链表的方法有多种，其中一种常见的方法是使用两个指针对链表进行调整，从而达到反转的效果。即通过改变节点的next指针的指向，将链表的方向翻转。

在原地反转链表的过程中，可以使用三个指针来进行操作。首先，设定一个指针pre指向当前节点的前一个节点，一个指针cur指向当前节点，一个指针next指向当前节点的后一个节点。

具体的原地反转链表的步骤如下：
1. 初始化pre为None，cur为链表的头节点。
2. 使用一个循环遍历链表，直到cur为None。
3. 在循环中，首先将next指针指向cur的下一个节点，以便在后面的操作中能够访问到该节点。
4. 将cur的next指针指向pre，即将当前节点的指针翻转。
5. 将pre指针指向cur，将cur指针指向next。
6. 重复步骤3-5，直到遍历完整个链表。

通过以上步骤，就可以实现链表的原地反转。这种方法的空间复杂度为O(1)，即只需要常数级别的额外空间。

引用提供了一个模型来说明整个链表的反转过程，引用中的图片也展示了通过四个步骤来实现链表的反转。这些方法都可以帮助我们更好地理解和实现链表的原地反转操作。<span class="em">1</span><span class="em">2</span><span class="em">3</span><span class="em">4</span>

相关问题

原地反转链表节点，C语言实现

原地反转链表是指在不额外分配新空间的情况下，改变链表节点自身的指针，使得链表从头开始到尾顺序翻转。以下是C语言的一个简单递归实现：

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

// 定义链表结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 反转链表的辅助函数
ListNode* reverseHelper(ListNode* head, ListNode* prev) {
    if (!head || !head->next) {
        // 如果链表为空或只有一个节点，则直接返回当前节点
        return head;
    }
    
    // 递归反转剩余部分，然后将当前节点连接到prev节点之后
    ListNode* curr = head->next;
    head->next = prev;   // 将当前节点的next指向前一个节点
    prev = head;         // 更新prev指向当前节点
    head = curr;          // 遍历到下一个节点

    // 继续递归处理
    return reverseHelper(curr, prev);
}

// 主函数用于创建链表并进行反转
void reverseList(ListNode** head_ref) {
    ListNode* newHead = reverseHelper(*head_ref, NULL); // 初始化prev为NULL
    *head_ref = newHead;                               // 更新原始链表头
}

// 创建链表示例
void createList(ListNode** head_ref, int arr[], int size) {
    ListNode* temp = *head_ref = (ListNode*)malloc(sizeof(ListNode));
    temp->val = arr[0];
    temp->next = NULL;

    for (int i = 1; i < size; i++) {
        ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
        newNode->val = arr[i];
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

// 打印链表
void printList(ListNode* node) {
    while (node) {
        printf("%d -> ", node->val);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    ListNode* head = NULL;

    createList(&head, arr, size);
    printf("Original list:\n");
    printList(head);

    reverseList(&head);
    printf("\nReversed list:\n");
    printList(head);

    return 0;
}

在这个例子中，`reverseList`函数会修改传入的链表头指针，使其指向新的头节点，实现了原地反转。

原地反转链表代码，C或C++

原地反转链表是指不创建新的节点，直接通过修改现有节点的指针来改变链表的顺序。这里是一个简单的C++实现，使用迭代方法：

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head; // 如果链表为空或只有一个元素，直接返回
    }

    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr != nullptr) {
        ListNode* temp = curr->next; // 记录当前节点的下一个节点
        curr->next = prev; // 将当前节点的next指向前一个节点
        prev = curr; // 更新前一个节点为当前节点
        curr = temp; // 移动到下一个节点
    }
    return prev; // 返回新头节点
}

// 测试函数
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

int main() {
    ListNode* list = new ListNode(1);
    list->next = new ListNode(2);
    list->next->next = new ListNode(3);

    std::cout << "Original List: ";
    printList(list);

    list = reverseList(list);

    std::cout << "Reversed List: ";
    printList(list);

    return 0;
}

这段代码首先检查链表是否为空或只有一个元素，然后通过三个指针prev、curr和temp来交换节点的前后位置。最后返回新的头节点，实现了链表的反转。