单链表的逆置数据结构

单链表的逆置，也称为链表反转，是指改变一个单链表中节点的顺序，使得原来的头节点变成新的尾节点，而原来的尾节点变成新的头节点。在不使用额外存储空间的情况下，可以通过迭代或递归的方法来实现这个过程。

**迭代法**：
1. 定义两个指针，一个指向当前节点（prev），一个指向当前节点的后继（current）。
2. 指针current开始时指向头节点，然后每次移动，同时更新prev指向current，current指向current的下一个节点，直到current为null。
3. 当current为null时，prev即为新的头节点。

**递归法**：
1. 定义一个辅助函数，传入当前节点（current）和前一个节点（prev，初始为null）。
2. 如果current为null，则返回，否则递归调用函数，将current的next赋值给current，然后返回current。
3. 最后返回null作为新的头节点，此时链表已经反转。

**相关问题--:**
1. 迭代法和递归法在链表逆置中的优缺点是什么？
2. 如何在Java中实现单链表的逆置？
3. 链表逆置后，原来的头节点和尾节点如何确定？

相关问题

头插法实现单链表逆置 数据结构C++版

头插法（即反转链表）是指通过在新链表的头部插入元素，逐步构建新的逆序链表。以下是使用C++实现单链表逆置的一种方法：

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 使用头插法逆置链表
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {  // 特殊情况：空链表或只有一个节点
        return head;
    }

    ListNode* prev = nullptr;  // 初始化前驱节点为NULL
    ListNode* curr = head;    // 当前节点初始化为头节点

    // 遍历链表，直到最后一个节点
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next;  // 保存当前节点的下一个节点
        curr->next = prev;  // 将当前节点的next指向前驱节点
        prev = curr;       // 移动前驱节点到当前节点
        curr = nextTemp;   // 移动当前节点到下一个节点
    }

    return prev;  // 返回逆序后的头节点
}

// 打印链表
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != nullptr) {
        std::cout << temp->val << " -> ";
        temp = temp->next;
    }
    std::cout << "nullptr\n";
}

int main() {
    // 创建一个示例链表
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

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

    head = reverseList(head);  // 逆置链表

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

    return 0;
}

在这个例子中，我们先检查链表是否为空或只有一个节点，如果是则直接返回。接着，我们通过三个指针prev、curr和nextTemp，分别表示前驱、当前和原始的下一个节点。在每次循环中，我们将curr的next指向前驱节点，然后移动prev和curr。当遍历完整个链表后，prev就是新的头节点。

数据结构：编写函数实现单链表逆置

数据结构是计算机中用来组织和存储数据的方式。单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

要实现单链表的逆置，可以编写一个函数来完成。以下是一个示例代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse_linked_list(head):
    if head is None or head.next is None:
        return head

    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

在这个示例中，我们定义了一个`Node`类来表示链表的节点。`reverse_linked_list`函数接受链表的头节点作为参数，并返回逆置后的链表的头节点。

函数中使用了三个指针`prev`、`curr`和`next_node`来进行逆置操作。首先，将`prev`初始化为`None`，`curr`初始化为头节点。然后，通过循环遍历链表，将当前节点的指针指向前一个节点，然后更新`prev`和`curr`指针，继续遍历下一个节点。最后返回逆置后的链表的头节点。