每天一算:Reverse Linked List II

LeetCode上第92号问题:反转链表II

题目

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4. 输出: 1->4->3->2->5->NULL

解题思路

Reverse Linked List 的延伸题。

可以考虑取出需要反转的这一小段链表,反转完后再插入到原先的链表中。

以本题为例:

变换的是2,3,4这三个点,那么我们可以先取出2,用front指针指向2,然后当取出3的时候,我们把3加到2的前面,把front指针前移到3,依次类推,到4后停止,这样我们得到一个新链表4->3->2, front指针指向4。

对于原链表来说,有两个点的位置很重要,需要用指针记录下来,分别是1和5,把新链表插入的时候需要这两个点的位置。

  • 用pre指针记录1的位置
  • 当4结点被取走后,5的位置需要记下来
  • 这样我们就可以把倒置后的那一小段链表加入到原链表中

动画演示

动画演示GIF加载有点慢,请稍等片刻^_^

参考代码

原文发布于微信公众号 - 五分钟学算法(blgczzz)

原文发表时间:2018-11-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏十月梦想

php字符串基本操作

字符串查找strstr(查找目标字符串,查找关键词),stristr(查找目标字符串,查找关键词)

7510
来自专栏柠檬先生

你不知道的javaScript笔记(4)

类型: JavaScript 有7种内置类型 空值 (null) 未定义(undefined) 布尔值(boolean) 数字(number) 字符串(stri...

23050
来自专栏闻道于事

Java之面向对象概述,类,构造方法,static,主方法,对象

一、面向对象概述 面向过程 “面向过程”(Procedure Oriented)是一种以过程为中心的编程思想。这些都是以什么正在发生为主要目标进行编程,不同于...

34650
来自专栏我和PYTHON有个约会

32.企业级开发进阶4:正则表达式

本节内容,要讲解的和我们的信息检索有关系,这一方面也是Python在目前非常流行的一个应用方向:爬虫。

10710
来自专栏转载gongluck的CSDN博客

python笔记:#008#变量的命名

变量的命名 目标 标识符和关键字 变量的命名规则 0.1 标识符和关键字 1.1 标识符 标示符就是程序员定义的 变量名、函数名 名字 需要有 见名知义 的...

38340
来自专栏java一日一条

那些经常被遗忘的 Java 面试题

静态内部类实际上与普通类(即类名必须与文件名一样的顶级类)一样,只是静态内部类在某一类的内部定义了而已,既然是类,要想使用就必须实例化。概念上与静态变量、静态方...

8010
来自专栏编程

Python入门基础连载(4)控制流

Python控制流语句有三种————if,for,while,有相关语言类似C,java的同学应该不会陌生的,下面我们就做下介绍: if语句 if语句用来检验一...

20260
来自专栏C语言C++游戏编程

有人@我,你有一份C语言基础大全手册要领取,快来拿!

前两天,有网友问了我一个关于C语言的问题,本着认真装逼的态度,我把大学时学过的C语言课本翻了一遍,终于找到了答案。整理后,现分享给大家!

19220
来自专栏诸葛青云的专栏

python入门:进来吧,给自己10分钟,这篇文章带你直接学会python

假设你希望学习Python这门语言,却苦于找不到一个简短而全面的入门教程。那么本教程将花费十分钟的时间带你走入Python的大门。本文的内容介于教程(Totur...

6000
来自专栏PPV课数据科学社区

走近 Python (类比 JS)

Python 是一门运用很广泛的语言,自动化脚本、爬虫,甚至在深度学习领域也都有 Python 的身影。作为一名前端开发者,也了解 ES6 中的很多特性借鉴自 ...

425100

扫码关注云+社区

领取腾讯云代金券