江苏 网站 备案,怎么利用招聘网站做薪酬调查,开发wordpress,电子商务企业网站建设规划#x1f49d;#x1f49d;#x1f49d;欢迎来到我的博客#xff0c;很高兴能够在这里和您见面#xff01;希望您在这里可以感受到一份轻松愉快的氛围#xff0c;不仅可以获得有趣的内容和知识#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学… 欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨ 博客目录 反转链表-力扣 206 题1.解法一2.解法二3.解法三4.解法四5.解法五6.解法六 反转链表-力扣 206 题 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 输入head [1,2,3,4,5]
输出[5,4,3,2,1]输入[1,2]
输出[2,1]输入[]
输出[]1.解法一
题解:
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:反转链表:定义前节点和当前节点:param head::return:pre, curr None, headwhile curr is not None:next curr.nextcurr.next prepre currcurr nextreturn pre2.解法二
构造一个新链表从旧链表依次拿到每个节点创建新节点添加至新链表头部完成后新链表即是倒序的
评价简单直白就是得新创建节点对象
// 创建新节点
public ListNode reverseList(ListNode o1) {//创建新的链表空节点ListNode n1 null;//设置临时节点,把o1指向pListNode p o1;while (p ! null) {//创建节点,新节点的下一个节点是新链表,并重置新链表的头部n1 new ListNode(p.val, n1);//移动旧链表的位置p p.next;}//因为重置了n1,直接返回n1return n1;
}3.解法三
与方法 2 类似构造一个新链表从旧链表头部移除节点添加到新链表头部完成后新链表即是倒序的区别在于原题目未提供节点外层的容器类这里提供一个另外一个区别是并不去构造新节点
评价更加面向对象如果实际写代码而非刷题更多会这么做
// 设计一个List
public ListNode reverseList(ListNode head) {//旧链表List o1 new List(head);//新链表List n1 new List(null);while (true) {//不断取旧链表的第一个元素final ListNode listNode o1.removeFirst();//如果旧链表为空则跳出循环if (listNode null) {break;}//将旧链表的第一个元素添加到新链表的头部n1.addFirst(listNode);}return n1.head;
}static class List {ListNode head;public List(ListNode head) {this.head head;}/*** 添加到头节点** param first*/public void addFirst(ListNode first) {//头节点的下一个节点是headfirst.next head;//重置headhead first;}/*** 删除头节点** return*/public ListNode removeFirst() {//此时的head是旧链表的head,需要截断头节点,并返回完整的节点ListNode first head;if (first ! null) {head first.next;}return first;}
}4.解法四
递归在递归时让 5 → 4 5 \rightarrow 4 5→4 4 → 3 4 \rightarrow 3 4→3 …
首先写一个递归方法返回值用来拿到最后一个节点
注意 1递归终止条件是 curr.next null目的是到最后一个节点就结束递归与之前递归遍历不一样注意 2需要考虑空链表即 p null 的情况
下面为伪码调用过程假设节点分别是 1 → 2 → 3 → 4 → 5 → n u l l 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1→2→3→4→5→null先忽略返回值
reverseList(ListNode p 1) {reverseList(ListNode p 2) {reverseList(ListNode p 3) {reverseList(ListNode p 4) {reverseList(ListNode p 5) {if (p null || p.next null) {return p; // 返回5}}// 此时p是4, p.next是5}// 此时p是3, p.next是4}// 此时p是2, p.next是3}// 此时p是1, p.next是2
}接下来从 p 4 开始要让 5 → 4 5 \rightarrow 4 5→4 4 → 3 4 \rightarrow 3 4→3 …
reverseList(ListNode p 1) {reverseList(ListNode p 2) {reverseList(ListNode p 3) {reverseList(ListNode p 4) {reverseList(ListNode p 5) {if (p null || p.next null) {return p; // 返回5}}// 此时p是4, p.next是5, 要让5指向4,代码写成 p.next.nextp// 还要注意4要指向 null, 否则就死链了}// 此时p是3, p.next是4}// 此时p是2, p.next是3}// 此时p是1, p.next是2
}最终解法
//递归
public ListNode reverseList(ListNode p) {if (p null || p.next null) {return p; // 最后节点}ListNode last reverseList(p.next);//这里最后一个节点是倒数第二个节点p.next.next p;//防止死循环,环形链表p.next null;return last;
}5.解法五
从链表每次拿到第二个节点将其从链表断开插入头部直至它为 null 结束
设置指针 o1(旧头)、n1(新头)、o2(旧老二)分别指向第一第一第二节点 n 1 o 1 1 → o 2 2 → 3 → 4 → 5 → n u l l \frac{n1 \ o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1n1 o1→2o2→3→4→5→null
将 o2 节点从链表断开即 o1 节点指向第三节点
$ \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$ o 2 2 \frac{o2}{2} 2o2
o2 节点链入链表头部即 o 2 2 → n 1 o 1 1 → 3 → 4 → 5 → n u l l \frac{o2}{2} \rightarrow \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2o2→1n1 o1→3→4→5→null
n1 指向 o2 n 1 o 2 2 → o 1 1 → 3 → 4 → 5 → n u l l \frac{n1 \ o2}{2} \rightarrow \frac{o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2n1 o2→1o1→3→4→5→null
o2 指向 o1 的下一个节点即 n 1 2 → o 1 1 → o 2 3 → 4 → 5 → n u l l \frac{n1}{2} \rightarrow \frac{o1}{1} \rightarrow \frac{o2}{3} \rightarrow 4 \rightarrow 5 \rightarrow null 2n1→1o1→3o2→4→5→null 重复以上 2 ∼ 5 2\sim5 2∼5 步直到 o2 指向 null 还应当考虑边界条件即链表中不满两个元素时无需走以上逻辑
/*** 不断把 o2 头插入 n1** param o1* return*/
public ListNode reverseList(ListNode o1) {// 1. 空链表 2. 一个元素if (o1 null || o1.next null) {return o1;}ListNode o2 o1.next;//新链表的指针ListNode n1 o1;while (o2 ! null) {//旧链表移动一位o1.next o2.next;//取出的数据的下一个节点指向新链表的头结点o2.next n1;//重置n1n1 o2;//重置o2o2 o1.next;}return n1;
}6.解法六
要点把链表分成两部分思路就是不断从链表 2 的头往链表 1 的头搬移
n1 指向 null代表新链表一开始没有元素o1 指向原链表的首节点 n 1 n u l l \frac{n1}{null} nulln1 o 1 1 → 2 → 3 → 4 → 5 → n u l l \frac{o1}{1} \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1o1→2→3→4→5→null
开始循环o2 指向原链表次节点 n 1 n u l l \frac{n1}{null} nulln1 o 1 1 → o 2 2 → 3 → 4 → 5 → n u l l \frac{o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1o1→2o2→3→4→5→null
搬移 o 1 1 → n 1 n u l l \frac{o1}{1} \rightarrow \frac{n1}{null} 1o1→nulln1 o 2 2 → 3 → 4 → 5 → n u l l \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2o2→3→4→5→null
指针复位 n 1 1 → n u l l \frac{n1}{1} \rightarrow null 1n1→null o 1 o 2 2 → 3 → 4 → 5 → n u l l \frac{o1 \ o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2o1 o2→3→4→5→null
重复 2 ∼ 4 2\sim4 2∼4 步当 o1 null 时退出循环
//不断把 o1 头插到 n1
public ListNode reverseList(ListNode o1) {if (o1 null || o1.next null) {return o1;}//创建空链表ListNode n1 null;while (o1 ! null) {ListNode o2 o1.next;//取出节点后指向新节点o1.next n1;//重置n1n1 o1;//重置o1o1 o2;}return n1;
}觉得有用的话点个赞 呗。 ❤️❤️❤️本人水平有限如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢! Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧
