如何实现链表元素的反转

反转链表是链表操作中一个经典的问题，也是面试中常见的考题。本文将从思路到实现一步步地讲解如何实现链表的反转，帮助初学者理解这一操作。我们将使用 C++ 代码演示具体实现，同时分析时间复杂度和空间复杂度。

问题定义

给定一个单链表，我们需要将链表的节点顺序反转。例如，链表 1 -> 2 -> -2 -> 3 经过反转后变为 3 -> -2 -> 2 -> 1。

思路分析

反转链表的核心在于修改每个节点的 next 指针，使其指向前一个节点。我们可以通过遍历链表，并逐个调整指针来实现链表的反转。这个过程的基本思路如下：

1. 先定义一个指针 cur 用于跟踪当前处理的节点，并将它初始化为 nullptr。
2. 遍历链表中的每个节点，将当前节点的 next 指针调整为指向 cur。
3. 更新 cur 和遍历指针，直到遍历完成。
4. 返回新的链表头，即原链表的尾节点。

这个过程可以在不使用额外存储空间的情况下完成链表的反转，因此其空间复杂度较低。

代码实现

以下是使用 C++ 实现链表反转的代码：

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int value;
    Node* next;
};

// 反转链表的函数
Node* reverseList(Node* node) {
    Node* cur = nullptr, *newNode = nullptr;
    while (node != nullptr) {
        newNode = node;             // 保存当前节点
        node = node->next;          // 移动到下一个节点
        newNode->next = cur;        // 将当前节点的 next 指向前一个节点
        cur = newNode;              // 更新 cur 为当前节点
    }
    return cur;                     // 返回新的头节点
}

int main() {
    // 创建一个示例链表：1 -> 2 -> -2 -> 3
    Node* head = new Node{1, new Node{2,  Node{,  Node{, }}}};

    
    Node* cur = head;
     (cur != ) {
        cout << cur->value << ;
        cur = cur->next;
    }
    cout << endl;

    
    cur = (head);

    
     (cur != ) {
        cout << cur->value << ;
        cur = cur->next;
    }
    cout << endl;

     ;
}