使用C++实现链表元素的反转_C/C++

问题定义

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

思路分析

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

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

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

代码实现

以下是使用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 ; 
}