💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。
输入:head = [1,2,3,4,5]输出:[5,4,3,2,1]输入:[1,2]输出:[2,1]输入:[]输出:[]
题解:
class Solution: def reverseList(self, head: Optional[Listnode]) -> Optional[ListNode]: """ 反转链表:定义前节点和当前节点 :param head: :return: """ pre, curr = None, head while curr is not None: next = curr.next curr.next = pre pre = curr curr = next return pre
构造一个新链表,从旧链表依次拿到每个节点,创建新节点添加至新链表头部,完成后新链表即是倒序的
评价:简单直白,就是得新创建节点对象
// 创建新节点public ListNode reverseList(ListNode o1) { //创建新的链表空节点 ListNode n1 = null; //设置临时节点,把o1指向p ListNode p = o1; while (p != null) { //创建节点,新节点的下一个节点是新链表,并重置新链表的头部 n1 = new ListNode(p.val, n1); //移动旧链表的位置 p = p.next; } //因为重置了n1,直接返回n1 return n1;}
与方法 2 类似,构造一个新链表,从旧链表头部移除节点,添加到新链表头部,完成后新链表即是倒序的,区别在于原题目未提供节点外层的容器类,这里提供一个,另外一个区别是并不去构造新节点
评价:更加面向对象,如果实际写代码而非刷题,更多会这么做
// 设计一个Listpublic 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; } public void addFirst(ListNode first) { //头节点的下一个节点是head first.next = head; //重置head head = first; } public ListNode removeFirst() { //此时的head是旧链表的head,需要截断头节点,并返回完整的节点 ListNode first = head; if (first != null) { head = first.next; } return first; }}
递归,在递归时让 5 → 4 5 \rightarrow 4 5→4, 4 → 3 4 \rightarrow 3 4→3 …
首先,写一个递归方法,返回值用来拿到最后一个节点
下面为伪码调用过程,假设节点分别是 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.next=p // 还要注意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;}
从链表每次拿到第二个节点,将其从链表断开,插入头部,直至它为 null 结束
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
$ \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$ ,o 2 2 \frac{o2}{2} 2o2
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
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
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
还应当考虑边界条件,即链表中不满两个元素时,无需走以上逻辑
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; //重置n1 n1 = o2; //重置o2 o2 = o1.next; } return n1;}
要点:把链表分成两部分,思路就是不断从链表 2 的头,往链表 1 的头搬移
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
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
//不断把 o1 头插到 n1public 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; //重置n1 n1 = o1; //重置o1 o1 = o2; } return n1;}
觉得有用的话点个赞
👍🏻
呗。
❤️❤️❤️本人水平有限,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍
🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙
来源地址:https://blog.csdn.net/qyj19920704/article/details/132581371
--结束END--
本文标题: 【数据结构-链表-01】反转链表
本文链接: https://www.lsjlt.com/news/383326.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0