力扣对应题目链接：206. 反转链表 - 力扣（LeetCode）

牛客对应题目链接：反转链表_牛客题霸_牛客网 (nowcoder.com)

核心考点 ：链表操作，思维缜密程度。

---

一、《剑指 Offer》内容

---

二、分析题目

解题思路（有较多解法）：

1. 定义三个指针，整体右移，边移动，边翻转，保证不会断链。
2. 可以采用头插思想进行翻转。
3. 递归。递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？

   假设链表为：n_1→…→n_k−1→n_k→n_k+1→…→n_m→∅

   若从节点 n_k+1 到 n_m 已经被反转，而我们正处于 n_k 。

   n_1→…→n_k−1→n_k→n_k+1←…←n_m
   我们希望 n_k+1 的下一个节点指向 n_k。

   所以，n_k->next->next=n_k。

   需要注意的是 n_1 的下一个节点必须指向 ∅。如果忽略了这一点，链表中可能会产生环。

---

三、代码

1、方法一（三指针）

//牛客AC代码
/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/ListNode* ReverseList(ListNode* head) {if(head==nullptr || head->next==nullptr)return head;ListNode* left=head;ListNode* mid=head->next;ListNode* right=mid->next;while(right){mid->next=left;left=mid;mid=right;right=right->next;}mid->next=left;head->next=nullptr;head=mid;return head;}
};//力扣AC代码
/*** 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) {ListNode* cur=head;ListNode* prev=nullptr;while(cur){ListNode* tmp=cur->next;cur->next=prev;prev=cur;cur=tmp;}return prev;}
};

---

2、方法二（插入）

//牛客AC代码
/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/ListNode* ReverseList(ListNode* head) {if(head==nullptr || head->next==nullptr)return head;ListNode* newHead=nullptr;while(head){ListNode* p=head;head=head->next;p->next=newHead;newHead=p;}return newHead;}
};//力扣AC代码
/*** 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) {if(head==nullptr || head->next==nullptr) return head;ListNode* newHead=nullptr;while(head){ListNode* p=head;head=head->next;p->next=newHead;newHead=p;}return newHead;}
};

---

3、扩展：方法三（递归） 

//力扣AC代码（推荐：写法一）
/*** 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) {if(head==nullptr || head->next==nullptr) return head;ListNode* newHead=reverseList(head->next);head->next->next=head;head->next=nullptr;return newHead;}
};//力扣AC代码（写法二）
/*** 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* reverse(ListNode* prev, ListNode* cur){if(cur==nullptr) return prev;ListNode* tmp=cur->next;cur->next=prev;return reverse(cur, tmp);}ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}
};