2.4 反转链表

问题

206. 反转链表 - 力扣（LeetCode）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：

head = [1,2,3,4,5]

输出：

[5,4,3,2,1]

示例 2：

输入：

head = [1,2]

输出：

[2,1]

示例 3：

输入：

head = []

输出：

[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

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

分析

考虑到单向链表的特殊迭代方式，迭代到下一个节点的时候，就无法“直接”获得上一个节点的信息（除非进行了保存），因此反转单向链表的操作和栈很类似，需要将先读取到的节点放入最里面。
而为了在遍历的时候能同时修改链表原本的指向，可以用多个指针实现。
具体来说，可以用三个指针分别表示前、中和后的位置，让中间的next指向之前的节点，然后整体往后移动重复操作，走完全程即可。

代码

 
// 迭代法
static ListNode* reverse_list_iterator(ListNode* head) 
{
    if (!head || !head->next) {
        return head;
    }
    ListNode *prev = nullptr;
    ListNode *next = head->next;
 
    while (head) {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}
 
// 递归法
static ListNode* reverse_list_recursion(ListNode* prev, ListNode* head)
{
    if (!head) {
        return nullptr;
    }
    if (!head->next) {
        head->next = prev;
        return head;
    }
    ListNode* next = head->next;
    head->next = prev;
 
    prev = head;
    head = next;
    return reverse_list_recursion(prev, head);
}
 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 递归法
        // return reverse_list_recursion(nullptr, head);
        // 迭代法
        return reverse_list_iterator(head);
    }
};

*****