【模板】如何实现链表元素的反转

反转链表是链表操作中一个经典的问题，也是面试中常见的考题。本文将从思路到实现一步步地讲解如何实现链表的反转，帮助初学者理解这一操作。我们将使用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, new Node{-2, new Node{3, nullptr}}}};
    
    // 打印链表反转前的值
    Node* cur = head;
    while(cur != nullptr) {
        cout << cur->value << " "; 
        cur = cur->next;
    }
    cout << endl;
    
    // 反转链表
    cur = reverseList(head);
    
    // 打印链表反转后的值
    while(cur != nullptr) {
        cout << cur->value << " "; 
        cur = cur->next;
    }
    cout << endl;
}

带头节点的链表

若链表带头节点，可使用以下方式反转链表，此时头节点不会跟随链表的反转而变化。

Node* reverseNode(Node* head) {
	Node* curNode = nullptr, *node = head -> next;
	while(node) {
		Node* temp = node;
		node = node -> next;
		temp -> next = curNode;
		curNode = temp;
	}
	head -> next = curNode;
	return ; 
}

代码讲解

• struct Node 定义了链表节点结构体，其中 value 存储节点值，next 存储指向下一个节点的指针。
• reverseList 函数用于反转链表。在此函数中，我们使用两个指针：cur 记录已反转部分链表的尾节点，node 遍历链表并依次调整指针。
• main 函数中创建一个简单链表，并分别在反转前后打印链表节点的值。

其他实现方式

递归反转链表

除了迭代法，我们还可以用递归的方式反转链表。递归法的思路是从链表末尾开始，将每个节点的 next 指针调整为其前一个节点，直到回到链表头节点。这种方法的代码实现如下：

Node* reverseListRecursive(Node* node, Node* prev = nullptr) {
    if (node == nullptr) return prev;    // 终止条件：到达链表末尾
    Node* next = node->next;             // 保存下一个节点
    node->next = prev;                   // 将当前节点的next指向前一个节点
    return reverseListRecursive(next, node);  // 递归处理下一个节点
}

比较两种方法

• 迭代法：简单直接，时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)。
• 递归法：实现上更简洁，但由于递归调用栈的存在，其空间复杂度为 O ( n ) O(n) O(n)，适用于链表长度较小的情况。递归深度过大会导致栈溢出问题。

时间和空间复杂度分析

对于上述代码，反转链表的时间复杂度和空间复杂度分别为：

• 时间复杂度： O ( n ) O(n) O(n)，其中 n n n 为链表节点数量。我们需要遍历链表中的每个节点，因此时间复杂度为 O ( n ) O(n) O(n)。
• 空间复杂度： O ( 1 ) O(1) O(1)，我们只使用了几个辅助指针来存储节点，没有额外占用大量空间。

总结

反转链表是链表操作中的基础知识，通过调整每个节点的指针可以实现高效的反转操作。本文介绍了迭代法和递归法两种反转链表的方式，并分析了各自的优缺点及复杂度，希望能对你有所帮助。