面试必备|单链表反转思路图形解析

01

单链表

链表玩的是指针操作,非常容易出错,尽管看似很简单。

先定义一种单链表,JAVA(或C#)描述的数据结构如下:

public class CLinkedList { public int val { get; set; } //简化起见,数据域直接定义为 int public CLinkedList next { get; set; } //next域,这就是链到下一个元素,或者理解为下一个元素的引用 }

再用最易理解的方式,初始化一个含有3个元素的链表,

CLinkedList mylist = new CLinkedList(); mylist.val = 1; mylist.next = new CLinkedList() { val = 2, next = new CLinkedList() { val = 3, next = null } };

图形化显示如下:

02

一种反转算法

我们试着将一个单链表反转,定义Reverse(list) API,实现此功能,比如对上面那个简单的链表,执行Reverse后的效果如下所述,当然颜色我们没有反转。

怎么实现呢?提供一种空间复杂度为O(1),时间复杂度为O(n)的算法。基本的实现思路如下:

  1. 创建一个新的节点newhead,其val为原链表头结点的val,其next为 null
  2. 定义next,指向原链表的第二个节点(头结点的next节点)
  3. 遍历,条件为: next != null: var tmpnext = next.next; //标记下next的next,为什么?接下来要破坏它,但是还要用它,所以标记它 next.next = newhead; // 当前的即将成为新链表头节点的next指向即将为旧的头节点newhead newhead = next; // newhead指向新构造的链表头节点,这样新链表成功增加了一个节点 next = tmpnext; //为下轮迭代做准备

4. 返回 newhead

03

反转算法图形显示

我们试着将一个单链表反转,定义Reverse(list) API,实现此功能,比如对如下链表进行反转操作:

算法图形化表达出来,步骤1和2的图形

步骤3的图形显示过程,全部罗列

  • 执行:tmpnext = next.next 后,
  • 执行:next.next = newhead 后,
  • 执行 newhead = next 后,此时newhead指向的链表增加了一个节点(就是next节点),2--->1的链表
  • 执行 next = tmpnext 后,next指向下一个添加到新链表头部的节点,即3节点。

再次走一遍上述的过程后,节点3又添加到2--->1这个链表上,newhead依然指向反转后的链表的头部,反转后的链表:3-->2--->1.

思路总结

  • next变量始终指向原链表的即将要添加到反转链表的节点,
  • newhead始终指向反转链表的头。
  • 每遍历一次,newhead增加一个节点,即next节点,直到next变为null为止。

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-12-28

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏破晓之歌

JAVA入门3-2(未完,待续) 原

List(序列)、Queue(队列)可重复排列有序的,Set(集)不可重复无序。list和set常用。

11850
来自专栏龙首琴剑庐

Java集合框架一览笔录

1、集合概念 集合类主要负责保存、盛装其他数据,因此集合类也被称为容器类。所以的集合类都位于java.util包下,后来为了处理多线程环境下的并发安全问题,ja...

30670
来自专栏数据结构与算法

BZOJ3585: mex(主席树)

Description   有一个长度为n的数组{a1,a2,...,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。 Input   第一行n,m...

43490
来自专栏C/C++基础

C++引用计数(reference counting)技术简介(3)

要想将引用计数施加到现有的实值对象Widget上,按照前面讨论的,都需要修改Winget类的源代码。但是,有时程序库的内容不是我们呢可以修改的,又该如何做呢?

8410
来自专栏IT可乐

Java中的增强 for 循环 foreach

  foreach 是 Java 中的一种语法糖,几乎每一种语言都有一些这样的语法糖来方便程序员进行开发,编译期间以特定的字节码或特定的方式来对这些语法进行处理...

24490
来自专栏闪电gogogo的专栏

Python入门学习(二)

1 字典 1.1 字典的创建和访问 字典不同于前述的序列类型,它是一种映射类型。它的引入是为了简化定义索引值和元素值存在特定关系的定义和访问问题。 字典的定义形...

33680
来自专栏aCloudDeveloper

经典排序之 插入排序

Author: bakari  Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之...

20080
来自专栏吴伟祥

logback高级特性使用 原

logback支持类似于占位符的变量替换功能,即如果输出的msg里面带有{}符号且括号中间不带其他字符,那么logback在构造LoggingEvent的时候,...

7720
来自专栏深度学习与计算机视觉

数据结构-静态链表及其插入删除操作

什么是静态链表 我们平常提及的链表一般指的是动态链表,是使用指针将一个一个的结点连起来,除了动态链表之外,还有静态链表,这种链表用数组来描述,主要为了解决没有指...

29090
来自专栏用户2442861的专栏

JAVA反射机制作用是什么

Java的反射机制是Java特性之一,反射机制是构建框架技术的基础所在。灵活掌握Java反射机制,对大家以后学习框架技术有很大的帮助。

1.8K20

扫码关注云+社区

领取腾讯云代金券