代码随想录刷题day11|（链表篇）206.翻转链表

目录

一、链表理论基础

二、翻转链表思路

双指针解法

递归解法

三、相关算法题目

四、总结

---

一、链表理论基础

代码随想录 (programmercarl.com)

二、翻转链表思路

两种方法：双指针解法和递归解法

双指针解法

首先定义一个指针curr，初始化为原链表头结点 head，用来遍历整个链表；定义一个临时指针temp，用来保存 curr.next；定义一个指针 prev，用来表示经过翻转后的链表的头结点；

该解法主要思想是，让 curr 从前往后遍历原链表，按照顺序将结点 依次插入 prev 指针所指向的结点之前，即 按照从后往前的顺序构建新链表，这样就可以试下原链表的翻转；

注意点：

1. 关于如何处理第一个节点的翻转：将 prev 和 temp 均初始化为 null，想象成在null之前插入结点，这样第一个结点的翻转和其他非头结点的翻转操作逻辑就可以一致；
2. 在进行翻转操作时，要注意结点插入时，更新边和指针值的顺序，容易出错，见下图；

递归解法

思想同双指针，代码也是类比双指针的来写；

结合代码来看：

class Solution {public ListNode reverseList(ListNode head) {// 递归 return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一个节点cur.next = prev;// 反转// 更新prev、cur位置// prev = cur;// cur = temp;return reverse(cur, temp);}
}

首先定义一个递归方法reverse来实现翻转链表，方法有两个参数：prev 和curr，指向结点和双指针中一样，（curr指向当前待处理结点，prev指向其前一个结点）；在递归体中，也需要定义一个临时指针temp 用来保存 curr.next；当 temp 保存好下一个结点位置，curr进行翻转，将当前节点的 next 指向前一个节点 prev，此时需要更新prev和curr的值，那么开始下一层递归调用；

每次递归时，都会将当前节点的 next 指向前一个节点，然后继续处理下一个节点，直到链表的末尾；

1.为什么初始参数设置为（null,head）？

在最初的调用中，prev 初始化为 null，curr初始化为 head；

2.为什么curr = null时终止返回？

当curr = null时，意味着已经遍历到链表的末尾，此时返回prev，即反转后的链表的头节点；这也是递归的出口；

3.递归体的下一层递归参数？

同双指针中的后两步操作，prev 更新为curr, curr更新为 temp，所以下一层递归调用中，此时两个参数分别是： prev -> curr，curr -> temp；

三、相关算法题目

206.翻转链表

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

双指针解法：

class Solution {public ListNode reverseList(ListNode head) {//双指针法ListNode prev = null;ListNode temp = null;ListNode curr = head;while(curr != null){temp = curr.next;curr.next = prev;prev = curr;curr = temp;}return prev;}
}

递归解法：见上

四、总结

1.递归解法思想要理解；

2.双指针中第一个节点为什么不用单独处理？prev、temp、curr的初始值为？⭐️

3.双指针中更新边的顺序；

4.掌握双指针解法以及思想；⭐️