C++数据结构与算法之反转链表的方法详解

C++数据结构与算法之反转链表的方法详解

在C++中，反转链表是一种常见的数据结构与算法技巧。在本文中，我们将详细讲解反转链表的实现过程以及常见的两种反转方法。

基本定义

在开始讲述反转链表算法之前，我们先介绍一下链表的基本定义。

链表是一种数据结构，其中每个节点包含一个数据元素和一个指向下一个节点的指针。下面是一个简单的链表的节点结构定义：

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

算法实现

方法一：迭代方法

这种方法可以用迭代的方式的反转链表的顺序。主要实现方式是用一个当前节点指针（current）和一个前置节点指针（prev）。

算法思路如下：

1. 初始状态下，prev为空指针，current指向链表的头结点。

2. 首先我们将current节点的next指针暂存到一个临时变量temp中，因为在我们反转节点的指针之后，当前节点的指针将指向前一个节点。

3. 接下来，让当前节点的next指针指向prev节点。

4. 现在我们将prev指针指向current节点。

5. 最后，current节点指向temp变量。

注意：在迭代过程中，需要将prev和current节点向右移动，即：prev = current; current = temp;

最后返回prev节点，就是反转链表后的头结点，如下所示：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* current = head;
        ListNode* temp = NULL;
        while (current != NULL) {
            temp = current->next;
            current->next = prev;
            prev = current;
            current = temp;
        }
        return prev;
    }
};

方法二：递归方法

递归是实现链表的一种更为自然的方法。

算法思路如下：

1. 如果当前节点为空或为最后一个节点，则返回当前节点。

2. 递归调用函数并传入下一个节点作为参数。

3. 现在我们拿到了下一个节点的结果，需要将当前节点的next指针指向它。

4. 然后返回反转后的链表的头结点。

如下代码所示：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }
};

示例说明

下面我们来看一下两种方法反转链表的两个示例。

示例一：

链表: 1->2->3->4->5->NULL

方法一反转后的链表: 5->4->3->2->1->NULL

方法二反转后的链表: 5->4->3->2->1->NULL

示例二：

链表: 1->NULL

方法一反转后的链表: 1->NULL

方法二反转后的链表: 1->NULL

本文讲解了链表的反转算法，包括迭代法和递归法，同时给出了两个示例。以上算法的时间复杂度均为O(n)，对于此类问题的解决可以套用这两种方法进行解决。

注意：在真正的开发中，我们需要考虑链表节点的内存的申请和释放问题，示例中省略了这一部分的内容。