`
810364804
  • 浏览: 773428 次
文章分类
社区版块
存档分类
最新评论

数据结构和算法设计专题之---单链表的逆序

 
阅读更多

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

图(1)初始状态

初始状态,prevNULLhead指向当前的头节点Anext指向A节点的下一个节点B。首先从A节点开始逆序,将A节点的next指针指向prev,因为prev的当前值是NULL,所以A节点就从链表中脱离出来了,然后移动headnext指针,使它们分别指向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

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

61LINK_NODE*ReverseLink(LINK_NODE*head)

62{

63 LINK_NODE*next;

64 LINK_NODE*prev=NULL;

65

66while(head!=NULL)

67{

68 next=head->next;

69 head->next=prev;

70 prev=head;

71 head=next;

72}

73

74returnprev;

75}

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

77LINK_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指针翻转过来。递归算法的完整代码如下:

77LINK_NODE*ReverseLink2(LINK_NODE*head)

78{

79 LINK_NODE*newHead;

80

81if((head==NULL)||(head->next==NULL))

82 returnhead;

83

84 newHead=ReverseLink2(head->next);/*递归部分*/

85 head->next->next=head;/*回朔部分*/

86 head->next=NULL;

87

88returnnewHead;

89}

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

分享到:
评论

相关推荐

    单链表的合并(递归-非递归)以及将单链表逆序

    单链表的合并(递归-非递归)以及将单链表逆序

    面向对象的单链表,在数据结构中使用

    面向对象的单链表,数据结构中使用,使用C语言!谢谢,祝使用愉快

    单链表实现就地逆序

    单链表实现就地逆序,简单的程序代码。详细的请关注数据结构论坛

    C语言实现单链表逆序与逆序输出实例

    主要介绍了C语言实现单链表逆序与逆序输出,是数据结构与算法中比较基础的重要内容,有必要加以牢固掌握,需要的朋友可以参考下

    单链表的建立、插入节点、删除节点、逆序、查找等等

    单链表的建立、插入节点、删除节点、逆序、查找等等,希望了可以给你们带来帮助

    C++ 实现带头节点的单链表

    在下最近在学数据结构,这是我写的一个单链表操作!希望可以帮到大家!

    头歌数据结构单链表的基本操作

    头歌数据结构单链表的基本操作 第1关单链表的插入操作 第2关单链表的删除操作 第3关单链表的按照序号查找值操作 第4关单链表的按照值查找结点位序的操作 第5关单链表的逆置操作 第6关两个有序单链表的合并操作 稳过 ...

    数据结构(C++)有关练习题

    31 习题9 排序------------------------------------------------------------------------------------34 第1部分 C++基本知识 各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学...

    数据结构Java语言描述课程实验设计(全文).docx

    通过Jv语言表现各种数据结构、实现相关算法是数据结构课程的难点之一,这给语言基础薄弱的学生完成实验带来很大困难,迫切需要在目标、过程、方法等各方面精心组织和设计实验。 数据结构Java语言描述课程实验设计...

    《数据结构 1800题》

    7. 数据结构是研讨数据的_(1)物理结构_和_(2)逻辑结构 _,以及它们之间的相互关系,并对与这种结构定义相应的_操作(3)_,设计出相应的(4)算法_。【西安电子科技大学 1998 二、2(3分)】 8. 一个算法具有 ...

    C语言经典算法——数据结构

    图的最小生成树 利用栈来实现单链表的逆序 Bresenham高效画线算法 约瑟夫环问题 二叉树的集合操作 递归算法的应用 ...

    知名公司数据结构笔试题及答案

    2.自己定义数据结构,写出程序:二叉树的前序遍历。 3.实现双向链表删除一个节点P,在节点P后插入一个节点,写出这两个函数。 4.下面哪种排序法对12354最快 a quick sort b.buble sort c.merge sort 5.哪种...

    [java版数据结构和算法系列之二]链表之一 –【单链】—手把手带你模拟链表的实现【内含BAT链表面试题实现】

    面试题3:逆序打印(这里使用栈的方式) 链表(Linked List)介绍【单链表篇】 链表包括:1.单链链表 ; 2.双链链表 ; 3. 环状链表  链表是有序的列表,但是它在内存中是存储如下   1)链表是以节

    JAVA单链表的简单操作(递增单链表插入数据,链表逆置,链表逆序合成)

    3、假设有两个按元素值递增有序的线性表 A 和 B,均以单链表作存储结构, 试编写算法将 A 表和 B 表归并成一个按元素值递减有序的线性表性表 C,并要求 利用原表的空间存放 C,并要求用尽可能少的时间完成。...

    数据结构中两个有序链表的链接

    ****假设有两个按元素值递增有序的线性表A和B,均以单链表作存储结构,试编写算法将A表和B表 *** ****归并成一个按元素值递减有序的线性表C,并要求利用原表的空间存放C。 *** *********************************...

    C语言经典算法

    图的最小生成树 上机训练题 简单的猫捉老鼠游戏 利用栈来实现单链表的逆序 ...Bresenham高效画线算法 简单的行编辑器 车站管理系统---自动计算费用 加注解的纸条问题新写的程序...(目录)数据结构在线教程 递归算法的应用

    线性表就地逆置,赫夫曼树,快速排序

    用VC编写的线性表就地逆置,赫夫曼树,快速排序的代码的实验报告

    链式存储结构的基本操作

    为了充分利用缓冲区的空间,往往将缓冲区设计成链式循环队列的结构,并为循环队列结构的缓冲区设置一个队首指针和一个队尾指针。每输入一个字符到缓冲区中,就将尾指针后移,链入缓冲区的循环队列之中;每输出一个字...

    线性表的链式存储结构..

    实验二 线性表的链式存储结构 题目:设计并实现以下算法:给出用单链表存储多项式的结构,利用后接法生成多项式的单链表结构,实现两个多项式相加的运算,并就地逆置相加后的多项式链式。1. 用户可以根据自己的需求...

    acwing和leetcode-Algorithm:acwinglabuladongleetcode

    8、模拟数据结构 数组模拟单链表 数组模拟双链表 数组模拟栈 数组模拟队列 9、单调栈 单调栈 10、单调队列 滑动窗口 11、KMP 12、Trie树 Trie字符串统计(1) Trie字符串统计(2) Trie字符串统计(3) 13、并查集 合并...

Global site tag (gtag.js) - Google Analytics