单链表逆序

2、 单链表逆序

第二个题目是很经典的“单链表逆序”问题。很多公司的面试题库中都有这道题,有的公司明确题目要求不能使用额外的节点存储空间,有的没有明确说明,但是如果面试者使用了额外的节点存储空间做中转,会得到一个比较低的分数。如何在不使用额外存储节点的情况下使一个单链表的所有节点逆序?我们先用迭代循环的思想来分析这个问题,链表的初始状态如图(1)所示:

图(1)初始状态

初始状态,prev是NULL,head指向当前的头节点A,next指向A节点的下一个节点B。首先从A节点开始逆序,将A节点的next指针指向prev,因为prev的当前值是NULL,所以A节点就从链表中脱离出来了,然后移动head和next指针,使它们分别指向B节点和B的下一个节点C(因为当前的next已经指向B节点了,因此修改A节点的next指针不会导致链表丢失)。逆向节点A之后,链表的状态如图(2)所示:

图(2)经过第一次迭代后的状态

从图(1)的初始状态到图(2)状态共做了四个操作,这四个操作的伪代码如下:

head->next = prev;

prev = head;

head = next;

next = head->next;

这四行伪代码就是循环算法的迭代体了,现在用这个迭代体对图(2)的状态再进行一轮迭代,就得到了图(3)的状态:

图(3)经过第二次迭代后的状态

那么循环终止条件呢?现在对图(3)的状态再迭代一次得到图(4)的状态:

图(4)经过第三次迭代后的状态

此时可以看出,在图(4)的基础上再进行一次迭代就可以完成链表的逆序,因此循环迭代的终止条件就是当前的head指针是NULL。

现在来总结一下,循环的初始条件是:

prev = NULL;

循环迭代体是:

next = head->next;

head->next = prev;

prev = head;

head = next;

循环终止条件是:

head == NULL

根据以上分析结果,逆序单链表的循环算法如下所示:

61 LINK_NODE *ReverseLink(LINK_NODE *head) 62 { 63 LINK_NODE *next; 64 LINK_NODE *prev = NULL; 65 66 while(head != NULL) 67 { 68 next = head->next; 69 head->next = prev; 70 prev = head; 71 head = next; 72 } 73 74 return prev; 75 }

现在,我们用递归的思想来分析这个问题。先假设有这样一个函数,可以将以head为头节点的单链表逆序,并返回新的头节点指针,应该是这个样子:

77 LINK_NODE *ReverseLink2(LINK_NODE *head)

现在利用ReverseLink2()对问题进行求解,将链表分为当前表头节点和其余节点,递归的思想就是,先将当前的表头节点从链表中拆出来,然后对剩余的节点进行逆序,最后将当前的表头节点连接到新链表的尾部。第一次递归调用ReverseLink2(head->next)函数时的状态如图(5)所示:

图(5)第一次递归状态图

这里边的关键点是头节点head的下一个节点head->next将是逆序后的新链表的尾节点,也就是说,被摘除的头接点head需要被连接到head->next才能完成整个链表的逆序,递归算法的核心就是一下几行代码:

84 newHead = ReverseLink2(head->next); /*递归部分*/ 85 head->next->next = head; /*回朔部分*/ 86 head->next = NULL;

现在顺着这个思路再进行一次递归,就得到第二次递归的状态图:

图(6)第二次递归状态图

再进行一次递归分析,就能清楚地看到递归终止条件了:

图(7)第三次递归状态图

递归终止条件就是链表只剩一个节点时直接返回这个节点的指针。可以看出这个算法的核心其实是在回朔部分,递归的目的是遍历到链表的尾节点,然后通过逐级回朔将节点的next指针翻转过来。递归算法的完整代码如下:

77 LINK_NODE *ReverseLink2(LINK_NODE *head) 78 { 79 LINK_NODE *newHead; 80 81 if((head == NULL) || (head->next == NULL)) 82 return head; 83 84 newHead = ReverseLink2(head->next); /*递归部分*/ 85 head->next->next = head; /*回朔部分*/ 86 head->next = NULL; 87 88 return newHead; 89 }

循环还是递归?这是个问题。当面对一个问题的时候,不能一概认为哪种算法好,哪种不好,而是要根据问题的类型和规模作出选择。对于线性数据结构,比较适合用迭代循环方法,而对于树状数据结构,比如二叉树,递归方法则非常简洁优雅。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏只喝牛奶的杀手

软件体验差到底算不算Bug?

The software doesn't do something that the product specification says it should ...

14150
来自专栏python爱好部落

低成本做接口测试

我之前尝试录制,将录制好的请求进行处理,然后post/get出去。 结果有人做了一个很完备的工具,比我的要完备,好得太多。它就是HttpRunner. 关键是很...

13040
来自专栏服务端思维

那些年,我们见过的 Java 服务端乱象

陈昌毅,花名常意,高德地图技术专家,2018年加入阿里巴巴,一直从事地图数据采集的相关工作。

9220
来自专栏只喝牛奶的杀手

KMP和String.indexOf

JDK源码中的String.indexOf是蛮力匹配的,可是JDK库的indexOf要比KMP快?算法不是让计算效率更高吗?JDK源码如下:

12720
来自专栏小黎子数据分析

WPF自学入门(十二)WPF MVVM模式提取函数

我们平时在写代码时为了不重复写代码,会进行复制代码或者写通用方法。今天我们就来把上传做的函数提取成为通用的方法调用。把上次写的函数提取为两个主要的文...

12220
来自专栏网站漏洞修复

网站漏洞解决与修复办法之seacms系统

临近9月底,seacms官方升级海洋cms系统到9.95版本,我们SINE安全在对其源码进行网站漏洞检测的时候发现问题,可导致全局变量被覆盖,后台可以存在越权漏...

13030
来自专栏全栈者

「数据可视化库王者」D3.js 极速上手到Vue应用

D3近年来一直是 JavaScript最重要的数据可视化库之一,在创建者 MikeBostock的维护下,前景依然无量,至少现在没有能打的:

49220
来自专栏只喝牛奶的杀手

Redis 哈希(Hash)

Redis hash 是一个string类型的field和value的映射表,hash特别适合用于存储对象。

10110
来自专栏孟君的编程札记

计算文件Checksum的几种方法

比如,我们到Apache网站上去下载用于操作Excel的依赖包 - Apache POI,就可以看到checksum:SHA-256, SHA-512,如下图所...

25420
来自专栏孟君的编程札记

给定整数数组,输出所有和为S的可能组合

如果给你一个题目,“给定一个整数数组和一个目标数S,如何输出该数组中所有和为S的可能组合?”,你会如何做呢?

11520

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励