C++程序实现链表反转

在学习数据结构和算法时，链表是一个非常重要的数据结构，反转链表也是常见的编程题目。在C++中，有很多种不同的实现方法，但有些实现方式可能会导致程序运行效率低下，甚至无法正确运行。本文将介绍如何正确地实现C++链表反转程序。

一、链表的定义

链表是一种基础数据结构，由一个个节点构成。每个节点包括数据和指向下一节点的指针。

C++ 中通过 struct 或 class 来定义节点，示例代码如下所示：

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

上述代码中定义了一个链表节点类 ListNode，包含一个整型成员变量 val 用于保存节点的数值，以及一个指针成员变量 next 指向下一个节点。在构造函数中对 val 进行初始化。

二、链表反转的实现

链表反转是一道经典的编程题目，常见的实现方式有三种：迭代法、递归法和头插法。

1. 迭代法

迭代法是一种常见的链表反转方法，它逐一遍历链表中的每个节点，并将每个节点的 next 指针指向其前一个节点。下面是迭代法的实现代码：

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;  // 前一个节点初始值为 NULL
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next;  // 记录下一个节点
        curr->next = prev;  // 指针翻转
        prev = curr;  // 更新前一个节点和当前节点
        curr = nextTemp;
    }
    return prev;  // 返回新链表的头节点
}

2. 递归法

递归法是一种简洁优美的链表反转方法，它通过递归回溯的方式遍历链表，并将每个节点的 next 指针指向其前一个节点。下面是递归法的实现代码：

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* p = reverseList(head->next);  // 递归遍历下一个节点
    head->next->next = head;  // 指针翻转
    head->next = nullptr;  // 处理头节点
    return p;  // 返回新链表的头节点
}

3. 头插法

头插法是一种简单直观的链表反转方法，它将当前节点插入到已反转部分的前面，形成新的链表。下面是头插法的实现代码：

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* newHead = new ListNode(-1);  // 申请哨兵节点
    while (head != nullptr) {
        ListNode* nextTemp = head->next;  // 记录下一个节点
        head->next = newHead->next;  // 插入当前节点到新链表头部
        newHead->next = head;
        head = nextTemp;  // 遍历下一个节点
    }
    return newHead->next;  // 返回新链表的头节点
}

注意：头插法虽然实现简单，但需要申请一个哨兵节点，增加了空间复杂度。由于需要频繁插入节点，头插法的时间复杂度为 $O(n^2)$ ，不如迭代法和递归法的时间复杂度高效。

三、代码测试与比较

为了验证不同实现方法的正确性和效率，下面对三种方法进行测试并比较。

1. 测试用例

假设有一个链表 1->2->3->4->5，预期反转后的链表为 5->4->3->2->1。

ListNode* createList() {
    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);
    return head;
}

void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = createList();
    cout << "原链表：";
    printList(head);
    head = reverseList(head);  // 反转链表
    cout << "新链表：";
    printList(head);
    return 0;
}