使用C++反转一个双向链表

1.前言

在许多编程面试中，反转一个链表是一个常见的面试题，因为这涉及到链表数据结构和基本算法。本文将介绍如何使用C++反转一个双向链表。

2.什么是双向链表

双向链表和普通的链表一样，它们都是由节点构成的链状结构。每个节点包含数据和一个指针，用于指向下一个节点。但与普通链表不同的是，双向链表中的每个节点还有一个指针，它指向前一个节点，这使得双向链表具有向前和向后遍历的能力。

2.1 双向链表数据结构

下面是一个C++实现的双向链表的节点数据结构：

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

可以看到，每个节点都有一个val值，一个指向前一个节点的prev指针，以及一个指向下一个节点的next指针。prev和next都是指向ListNode类型的指针。在构造函数中，我们将prev和next指针初始化为nullptr。

2.2 双向链表示意图

下面的图示展示了一个双向链表的示意图，可以看到每个节点都有两个指针，一个指向上一个节点，一个指向下一个节点。


3.反转双向链表

反转一个双向链表意味着将每个节点的指针方向都反转，从而得到一个完全相反的链表。下面是C++代码的实现：

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

我们使用三个指针prev、curr和nextNode来反转双向链表。prev指针始终指向新链表的头节点的前一个节点，curr指针指向当前正在操作的节点，nextNode指向curr节点的下一个节点。在while循环中，我们先把nextNode指向curr->next，以便我们可以在下一步中移动curr指针。然后我们将curr的prev指针指向nextNode，以反转节点之间的指针方向。接下来，我们将curr的next指针指向prev，将prev指针指向curr，然后将curr指针移动到nextNode节点。最后，我们将prev指针指向反转后的新链表的头节点，即原链表的尾节点。最后返回prev指针。

4.反转双向链表的示意图

下面的图示展示了一个双向链表反转前后的示意图。


反转双向链表是一个常用的算法问题，在C++中实现它需要一些指针操作和基本的链表知识。掌握这个算法可以帮助你更好地理解链表数据结构并应用它们。