使用C++反转一个链表

1. 反转链表基本概念

反转一个链表，其实就是将链表中的每个节点的指针方向从原来的下一个节点改为指向上一个节点，最后将原来指向下一个节点的指针指向NULL即可

1.1 单向链表数据结构

首先，我们需要了解单向链表的数据结构，单向链表是一种常见的数据结构，其通过指针将所有元素依次链接在一起组成一个链表，每个节点除了保存所存储的元素之外，还需要保存一个指向下一个节点的指针。下面是单向链表的数据结构：

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

其中val保存节点的值，next指向下一个节点的地址，当节点为链表的尾部时，节点的next指向NULL

1.2 反转链表思路

反转一个链表，从链表头开始，依次遍历链表中的每个节点，并把它们反转。

假设我们要反转如下的链表：

1 -> 2 -> 3 -> 4 -> NULL

首先，我们定义三个指针，分别指向当前节点curr，当前节点的上一个节点prev和当前节点的下一个节点next，初始时，prev和next都指向NULL，curr指向链表的头部，如下图所示：

NULL <- 1    2 -> 3 -> 4 -> NULL
      curr  prev  next

在遍历链表中的每个节点时，我们需要做以下操作：

先将curr的下一个节点保存到next指针中

然后将curr的下一个节点指向pre

接着将pre指向当前节点curr，即pre=curr

最后将当前节点指向next，即curr=next

每个节点的操作都是相同的，通过不断地执行上述步骤，我们可以得到反转后的链表：

NULL <- 1 <- 2 <- 3 <- 4

2. C++反转一个链表实现

了解了反转链表的基本思路后，我们就可以来实现C++中反转一个链表了。下面是实现代码：

ListNode* reverseList(ListNode* head) {
    ListNode* curr = head;
    ListNode* prev = NULL;
    ListNode* next = NULL;
    while(curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

首先，我们定义了三个指向ListNode的指针curr，prev，next，这三个指针都被初始化为NULL，然后我们开始遍历链表中的每个节点。在每次遍历时，我们将当前节点的next指针保存在next指针中，然后将当前节点的next指针指向prev，然后将prev指向当前节点curr，最后将curr指向next。当遍历完整个链表后，我们返回prev指针，它指向的是反转后的链表的头结点。

3. C++反转链表完整代码示例

为了更好地理解反转链表的实现过程，下面给出一份完整的代码实现，其中包括了对反转链表方法的详细解释：

#include <iostream>
using namespace std;
struct ListNode{
    int val; //链表节点的值
    ListNode* next; //指向下一个节点的指针
    ListNode(int x): val(x), next(NULL) {} //构造函数
};
ListNode* reverseList(ListNode* head) {
    ListNode* curr = head; //从头部开始遍历
    ListNode* prev = NULL; //prev指针初始化为NULL
    ListNode* next = NULL; //next指针初始化为NULL
    while(curr) {
        next = curr->next; //将curr的下一个节点保存到next指针中
        curr->next = prev; //将curr的指针方向反转
        prev = curr; //将prev指针指向当前节点
        curr = next; //将curr指针指向下一个节点
    }
    return prev; //返回反转后的链表
}
int main() {
    ListNode* head = new ListNode(1); //创建链表头部节点
    ListNode* second = new ListNode(2); //创建链表第二个节点
    ListNode* third = new ListNode(3); //创建链表第三个节点
    
    head->next = second; //头部节点指向第二个节点
    second->next = third; //第二个节点指向第三个节点
    
    ListNode* reverseHead = reverseList(head); //反转链表
    
    while(reverseHead) { //遍历并打印反转后的链表
        cout << reverseHead->val << " "; //打印节点的值
        reverseHead = reverseHead->next; //将指针指向下一个节点
    }
    cout << endl;
    return 0;
}

这段代码定义了一个链表数据结构ListNode，并定义了一个reverseList函数来反转链表。在main函数中，我们首先用new创建了链表的头部与两个其他节点，并将它们依次链接在一起，然后调用reverseList函数来反转链表，最后遍历并打印反转后的链表。

4. 总结

本文详细介绍了反转链表的基本概念，以及如何使用C++实现反转链表。反转一个链表的基本思路是定义三个指针curr，prev，next，分别指向当前节点、当前节点的上一个节点和当前节点的下一个节点，在遍历链表中的每个节点时，依次执行下面四个步骤：

将curr的下一个节点保存到next指针中

将curr的下一个节点指向pre

将pre指向当前节点curr，即pre=curr

将当前节点指向next，即curr=next

通过不断执行上述四个步骤，我们可以得到反转后的链表。反转链表函数的实现比较简单，而且时间复杂度为O(n)，所以它在链表相关的问题中经常被使用到。