当前位置: 首页 > news >正文

反转链表-leetcode

题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

img

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

img

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

解法一

思路:

迭代置换,p,q,r三个指针,转换q.next=p,之后p=q,q=r,r=r.next。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) return head;ListNode p,q,r;p = head;q=head.next;r=head.next.next;while(true){if(p==head)p.next=null;q.next=p;p=q;q=r;if(q==null) break;r=r.next;}return p;}
}

解法二

思路:

来自官方解答。

递归版本稍微复杂一些,其关键在于反向工作。假设链表的其余部分已经被反转,现在应该反转它前面的部分。设链表为:

image-20250928191656820

若从节点 image-20250928191725095image-20250928191741891 已经被反转,而我们正处于 image-20250928191754300

image-20250928191804311

我们希望 image-20250928191823248 的下一个节点指向 image-20250928191856362

所以,image-20250928191927213

需要注意的是 image-20250928191948351 的下一个节点必须指向 ∅。如果忽略了这一点,链表中可能会产生环

代码:

class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}
http://www.hskmm.com/?act=detail&tid=20211

相关文章:

  • 第45篇:AI+交通:自动驾驶、智能交通管理与出行优化 - 实践
  • three角度处理:1.角度、弧度归一(0,2PI),2.两个角度之间的最小夹角
  • 软件工程技术第一次作业
  • 在macos下Termius无法连接局域网主机的一个经常出现但又很难排查的问题
  • 《痞子衡嵌入式半月刊》 第 119 期
  • 20243907张驰
  • vim学习使用笔记
  • c#造个轮子-取色器TakeColor(附源码)
  • 实用指南:计算机视觉:人脸关键点定位与轮廓绘制
  • JVM调优工具详解及调优实战
  • 双链表
  • ubuntu系统挂载硬盘
  • 代码之美-代码整洁之道
  • Chrome for Testing availability
  • RAG实践:一文掌握大模型RAG过程
  • 递归算法实践--到仓合单助力京东物流提效增收
  • 计算机视觉(opencv)练习——抠图(图像裁剪与轮廓提取) - 详解
  • 深入解析:@scqilin/phone-ui 手机外观组件库
  • Tita项目与绩效一体化管理:驱动企业效能跃升的数字化引擎
  • 第七篇
  • labview打包应用
  • Day23抽象类
  • ES 是否有类似mysql explain的语句诊断用法
  • 让每次语音唤醒都可靠,公牛沐光重构可观测体系
  • 【2025-09-27】连岳摘抄
  • Python 爬虫 HTTPS 实战,requests httpx aiohttp 抓取技巧、证书问题与抓包调试全流程 - 教程
  • Codeforces 补题笔记
  • 使用 Python 基于Ollama构建个人私有知识库(AI生成)
  • Codeforces Round 1048 (Div. 2) 补题笔记
  • 【RabbitMQ】消息可靠性保障