【数据结构与算法】206.反转链表(LeetCode)

反转链表

问题描述

给定单链表的头节点 head,要求反转链表并返回反转后的链表头节点。

题目传送门

在这里插入图片描述

思路一:创建新链表头插法

核心思路:创建新链表,将原链表中的节点拿来头插

算法步骤

  1. 初始化新链表头节点 newheadNULL
  2. 使用指针 pcur 遍历原链表
  3. 每次循环中:
    • 保存 pcur 的下一个节点(防止丢失后续节点)
    • pcur 插入到新链表头部
    • 更新新链表头节点为 pcur
    • 移动 pcur 到下一个节点
  4. pcurNULL 时,返回新链表头节点

如图:

在这里插入图片描述

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead,*pcur;newhead=NULL;pcur=head;while(pcur){struct ListNode* tmp=pcur->next;//先保存pcur的下一个节点 头插时会改变pcur的指向//头插pcur->next=newhead;newhead=pcur;pcur=tmp;}return newhead;}

复杂度分析

  • 时间复杂度:O(n),只需遍历链表一次
  • 空间复杂度:O(1),仅使用固定数量的指针变量

思路二:三个指针法

指针定义

  • n1:指向已反转部分的最后一个节点(初始为NULL)
  • n2:指向当前待反转节点(初始为头节点)
  • n3:指向下一个待反转节点(初始为头节点的下一个节点)

算法步骤

  1. 初始化三个指针:n1 = NULL, n2 = head
  2. 如果链表非空,则设置 n3 = head->next
  3. 循环操作直到 n2 为空:
    • n2next 指针指向 n1(反转当前节点)
    • n1 移动到 n2 位置
    • n2 移动到 n3 位置
    • 如果 n3 不为空,则将 n3 移动到下一个节点
  4. 返回 n1(即新链表的头节点)

如图

在这里插入图片描述
)

可以看到循环结束的条件是n2为空

struct ListNode* reverseList(struct ListNode* head){struct ListNode* n1,*n2,*n3;n1=NULL;n2=head;if(n2)//判断链表是否为空n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)//判断n3是否为空n3=n3->next;}return n1;
}

注意事项

  1. 边界条件处理
    • 空链表:直接返回 NULL
    • 单节点链表:无需反转,直接返回头节点
  2. 指针移动顺序
    • 必须先更新 n1n2,再更新 n3
    • 更新 n3 前需要检查其是否为空,避免空指针异常

复杂度分析

  • 时间复杂度:O(n),只需遍历链表一次

  • 空间复杂度:O(1),仅使用固定数量的指针变量

    方法对比分析

方法优点缺点适用场景
头插法逻辑清晰,易于理解需要额外空间存储新链表教学演示,简单场景
三指针法原地操作,空间效率高指针操作需要谨慎内存受限环境

总结

反转链表是链表操作中的经典问题,2种方法各有特点:

  1. 头插法:直观易懂,适合初学者理解链表反转的基本原理

  2. 三指针法:空间效率最优,适合实际开发中的内存敏感场景

受限环境

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/575.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

源表=电源+数字表?一文看懂SMU源表 2025-04-14

源表(Source Meter Unit, SMU)广泛用于半导体器件、材料、医疗、发光器件与光通信等行业,测量器件的伏安(I-V)特性曲线、绝缘材料的电阻值(电阻率)、电容的绝缘电阻(漏电流)、光电器件的暗电流或者L-I-V等。 源表的名称已经清晰的告诉我们,它包含了高精度电源输出和…

探索飞算 JavaAI 进阶:解锁高效Java开发的新维度

前引:在当今快速迭代的软件开发领域,Java作为企业级应用的基石,持续推动着技术创新。随着性能需求的提升,“飞算JAVA”应运而生,它融合了现代优化理念,为开发者提供了一套简洁、高效的解决方案。本文将深入…

亿级流量下的缓存架构设计:Redis+Caffeine多级缓存实战

亿级流量下的缓存架构设计:RedisCaffeine多级缓存实战 一、为什么需要多级缓存? 在亿级流量场景下,单纯依赖Redis会遇到三大瓶颈:网络延迟:Redis远程访问通常需要1-5ms,QPS超过10万时成为瓶颈资源成本&…

从就绪到终止:操作系统进程状态转换指南

前言: 在操作系统的核心机制中,进程管理是至关重要的组成部分。进程在其生命周期中会经历多种状态的变化,如创建、就绪、运行、阻塞、挂起和终止等。理解这些状态及其转换关系,不仅有助于掌握操作系统的调度原理,也能为…

chatgpt是怎么诞生的,详解GPT1到GPT4的演化之路及相关背景知识

人工智能革命正在发生,我们是何其幸运的一代,能亲眼见证人类/机器智能的大爆发。 仅仅作为这场革命的看客显然是有些遗憾的,如何进一步了解它? 本文将讨论chatgpt的诞生过程,串联起OpenAI发表的一系列重要论文&#…

GitHub信息收集

目录 简介 一、入门搜索技巧 1. 基本关键词搜索 2. 文件类型限定搜索 3. 用户/组织定向搜索 二、精准定位技巧 1. 组合搜索条件 2. 排除干扰结果 3. 路径限定搜索 三、防御建议 四、法律与道德提醒 简介 GitHub作为全球最大的代码托管平台,存储着数十亿…

2025.07.09华为机考真题解析-第一题100分

📌 点击直达笔试专栏 👉《大厂笔试突围》 💻 春秋招笔试突围在线OJ 👉 笔试突围OJ 01. 花园灯具照明设计 问题描述 K小姐正在为她的私人花园设计照明系统。花园是一条长廊,由 n n n

Sophix、Tinker 和 Robust 三大主流 Android 热修复框架的详细对比

以下是 Sophix、Tinker 和 Robust 三大主流 Android 热修复框架的详细对比,从技术原理、功能支持、性能表现到适用场景的全方位分析:一、核心原理对比特性SophixTinkerRobust修复方式混合模式(即时生效 冷启动)冷启动生效&#x…

SSRF(ctfshow)

web351-358这部分的题目都是明文的&#xff0c;按照题目要求绕过就行了<?php error_reporting(0); highlight_file(__FILE__); $url$_POST[url]; $xparse_url($url); if($x[scheme]http||$x[scheme]https){ if(!preg_match(/localhost|127\.0\.|\。/i, $url)){ $chcurl_ini…

虚拟储能与分布式光伏协同优化:新型电力系统的灵活性解决方案

安科瑞顾强摘要&#xff1a; 在全球能源结构向低碳化、智能化加速转型的背景下&#xff0c;分布式光伏的大规模接入为电力系统带来机遇的同时&#xff0c;也因其波动性与间歇性带来了运行挑战。本文聚焦于虚拟储能系统&#xff08;Virtual Energy Storage System, VESS&#xf…

Python-文件操作

1 需求2 接口3 示例open 函数是 Python 的内置函数&#xff0c;主要用于文件的读写操作。file&#xff1a;此参数代表文件路径&#xff0c;既可以是绝对路径&#xff0c;也可以是相对路径。就像你代码里的 cfg.ini&#xff0c;这是一个相对路径&#xff0c;表示当前目录下的 cf…

【图像处理基石】图像超分辨率有哪些研究进展值得关注?

近年来&#xff0c;图像超分辨率&#xff08;SR&#xff09;领域在深度学习技术的推动下取得了显著进展&#xff0c;尤其在模型架构优化、计算效率提升和真实场景适应性等方面涌现出诸多创新。以下是基于最新研究的核心进展梳理&#xff1a; 一、高效大图像处理&#xff1a;像素…