网站建设推广方案策划书,网站宝搭建网站环境,个人网站制作模板,红鹊豆网络网站站建设目录
一、链表理论基础
二、翻转链表思路
双指针解法
递归解法
三、相关算法题目
四、总结 一、链表理论基础
代码随想录 (programmercarl.com)
二、翻转链表思路
两种方法#xff1a;双指针解法和递归解法
双指针解法
首先定义一个指针curr#xff0c;初始化为原…目录
一、链表理论基础
二、翻转链表思路
双指针解法
递归解法
三、相关算法题目
四、总结 一、链表理论基础
代码随想录 (programmercarl.com)
二、翻转链表思路
两种方法双指针解法和递归解法
双指针解法
首先定义一个指针curr初始化为原链表头结点 head用来遍历整个链表定义一个临时指针temp用来保存 curr.next定义一个指针 prev用来表示经过翻转后的链表的头结点
该解法主要思想是让 curr 从前往后遍历原链表按照顺序将结点 依次插入 prev 指针所指向的结点之前即 按照从后往前的顺序构建新链表这样就可以试下原链表的翻转
注意点
关于如何处理第一个节点的翻转将 prev 和 temp 均初始化为 null想象成在null之前插入结点这样第一个结点的翻转和其他非头结点的翻转操作逻辑就可以一致在进行翻转操作时要注意结点插入时更新边和指针值的顺序容易出错见下图 递归解法
思想同双指针代码也是类比双指针的来写
结合代码来看
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 初始化为 nullcurr初始化为 head
2.为什么curr null时终止返回
当curr null时意味着已经遍历到链表的末尾此时返回prev即反转后的链表的头节点这也是递归的出口
3.递归体的下一层递归参数
同双指针中的后两步操作prev 更新为curr, curr更新为 temp所以下一层递归调用中此时两个参数分别是 prev - currcurr - 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.掌握双指针解法以及思想⭐️
