C++实现LeetCode(206.倒置链表)

首先，LeetCode的题目206是一个非常经典的链表反转问题。可以使用迭代和递归两种方式来实现。

1. 题目描述

反转一个单链表。

示例 1:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

示例 2:

输入: NULL

输出: NULL

2. 迭代实现

可以通过迭代方式，依次将当前节点的next指向前面的节点，直到所有节点都被反转。详细代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        ListNode* prev = nullptr, *curr = head;

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

        return prev;
    }
};

3. 递归实现

可以通过递归方式，依次反转每个节点，并将当前节点的next节点指向前面的节点。详细代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return p;
    }
};

4. 示例说明

示例 1：

输入：1->2->3->4->5->NULL

输出：5->4->3->2->1->NULL

通过迭代的方式实现：

初始化：prev = nullptr, curr = 1->2->3->4->5->NULL
第一次循环：curr = 2->3->4->5->NULL, prev = 1->NULL
第二次循环：curr = 3->4->5->NULL, prev = 2->1->NULL
第三次循环：curr = 4->5->NULL, prev = 3->2->1->NULL
第四次循环：curr = 5->NULL, prev = 4->3->2->1->NULL
第五次循环：curr = NULL, prev = 5->4->3->2->1->NULL
返回结果：prev = 5->4->3->2->1->NULL

通过递归的方式实现：

reverseList(1->2->3->4->5->NULL) -> reverseList(2->3->4->5->NULL) -> reverseList(3->4->5->NULL) -> reverseList(4->5->NULL) -> reverseList(5->NULL) 

函数返回 5->4->3->2->1->NULL，整个过程都是通过递归调用数据达到反转的目的。

5. 总结

C++实现LeetCode(206.倒置链表)问题的关键在于理解链表反转的本质和特点，能够使用迭代或递归的方式实现。同时，本题也是链表反转的模板题目，对于类似的问题，同样可以套用反转链表的思想进行解题。