力扣对应题目链接：206. 反转链表 - 力扣（LeetCode）
牛客对应题目链接：反转链表_牛客题霸_牛客网 (nowcoder.com)
核心考点 ：链表操作，思维缜密程度。
一、《剑指 Offer》内容
二、分析题目
解题思路（有较多解法）：
- 定义三个指针，整体右移，边移动，边翻转，保证不会断链。
- 可以采用头插思想进行翻转。
- 递归。递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？假设链表为：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); } };
