题目

反转一个单链表。

示例:

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

进阶:

• 你可以迭代或递归地反转链表。

分析与题解

双指针法

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

ListNode* tmp; // 用于记录当前节点的下一节点
ListNode* pre = nullptr;
ListNode* cur = head;

因为接下来要开始改变 cur->next 的指向了，首先要把 cur->next 节点用tmp指针保存一下，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时pre指针就指向了新的头结点。完整代码如下：

/**
 * 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* tmp; // 用于记录当前节点的下一节点
        ListNode* pre = nullptr;
        ListNode* cur = head;

        while (cur != nullptr) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        // 退出循环时，cur为空节点
        return pre;
    }
};

递归

其实两种方法的本质是一样的，关键是没有更改当前节点cur的next节点后，我们需要同时更新cur和pre节点，而递归将每次循环的更新以函数形参的形式进行展现。代码如下：

/**
 * 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) {
        return reverse(nullptr, head);
    }

    ListNode* reverse(ListNode* pre, ListNode* cur) {
        // 递归中止条件
        if (cur == nullptr) return pre;

        // 先存储原本cur的next节点
        ListNode* tmp = cur->next;
        cur->next = pre;
        // pre = cur;
        // cur = tmp;
        // 递归等效于执行上述两行代码
        return reverse(cur, tmp);
    }
};

206. 反转链表（C++）

原文：https://www.cnblogs.com/buryinshadow/p/14220708.html