反转单链表【图文详解】
问题描述:
给你单链表的头结点head，请你反转链表，并返回反转后的链表。
我在这里详细讲解两种经典解法
(双指针)迭代求解:
双指针法是最好理解的，无非一前一后，一起走同时改变局部指向
- 定义两个指针，让pre在前，cur在后
- 每一次让pre的next指向cur，即完成一次局部的指向转变
- 局部完成一次后，两个指针一起向后走(这中间需要一个临时指针用来保存pre的下一个位置，与交换两个数的思想一致)
- 当pre走到表尾，完成了最后一个转换，循环结束
循环内部示意图:
代码示例：
class Solution {public: ListNode* reverseList(ListNode* head) { //双指针迭代 ListNode *pre=head; ListNode *cur=nullptr; while(pre!=nullptr) { ListNode *tmp=pre->next; pre->next=cur; //改变指向 cur=pre; //pre cur向后走 pre=tmp; } return cur; }};- 时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
- 空间复杂度：O(1)。
上述方法务必掌握，下来我们讲解这道题一种很骚的解法：递归(不容易理解)
递归求解：
思路解释:
既然要反转单链表，我们就可以一直走到表尾，从表尾开始向前改变指向，这个时候就可以使用递归函数。
-
使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点,记作 newhead
-
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next->next 指针指向当前节点
-
同时让当前节点的next指向空，完成了一次局部反转
-
当递归函数全部出栈后，完成反转
先给代码:对照代码用图来解释
class Solution {public: ListNode* reverseList(ListNode* head) { if(head==nullptr||head->next==nullptr) { return head; } ListNode *newhead=reverseList(head->next); //如果链表是 1->2->3->4->5，那么此时的newhead就是5//而head是4，head的下一个是5，下下一个是空//所以head.next.next 就是5->4 head->next->next=head; //防止链表循环，需要将head.next设置为空 head->next=nullptr; //每层递归函数都返回newhead，也就是最后一个节点 return newhead; //newhead一直不变，返回的这个newhead就是新链表的头节点 }};
看懂这张我总结的图，递归方法就一定可以理解了!
-
时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
-
空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
如果觉得文章写得还不错，麻烦点个赞支持一下，欢迎评论，互相学习！