线性链表 反转 -(递归与非递归算法)_20230420

这篇具有很好参考价值的文章主要介绍了线性链表 反转 -(递归与非递归算法)_20230420。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

线性链表 反转 -(递归与非递归算法)_20230420

  1. 前言

线性链表反转是非常有趣的算法,它可以采用多种方式实现,比较简洁的方法是递归反转;传统的方式是利用迭代反转,设定三个变量,采用类似滚动数组的方式,实现线性表的反转;利用线性表头部插入方法也不失为一种直观有效的方式,这种情况下需要重新建立线性链表,在遍历目标链表的同时,不断把元素插入新的线性链表的头部,从而实现反转;最后的方式是就地反转,不用设定新的线性链表,在本身线性链表的基础之上,实现元素的反转,这种方式与头插法类似,过程中需要至少三个变量保存链表的头部,待处理结点和链表的尾部。

具体看一个实际例子。假定给到下图的线性链表,要求通过合适的算法,实现线性链表的反转。反转前链表结构,

线性链表 反转 -(递归与非递归算法)_20230420

反转的过程本质上不是重新建立结点的过程,而是重新链接其next结点以及设定新的头结点的过程,这个过程中结点地址和内容本身不会发生变化,发生变化的是结点中的next指针域和头结点的位置。通过一系列的算法操作,重新建立next链接后的线性链表实现了反转。

线性链表 反转 -(递归与非递归算法)_20230420

  1. 线性表反转不同算法实现

2.1.线性链表建立

递归算法之前,需要先建立简单的线性链表,线性链表一般由两部分沟通,两个域分别包含数据和指向下一结点的指针。Value域存放数据对象,next域存放指针,指针指向下一个结点。

链表的建立通过函数build_linked_list实现,具体模式采用尾部插入方法,如果链表为空,那么就作为链表的头结点,否则通过循环寻找需要插入位置的前置结点,然后把前置结点的next指向待插入结点即可(p->next = new_ptr)。

线性链表 反转 -(递归与非递归算法)_20230420

建立链表的具体算法实现,

typedef struct Link_Node
{
    int value;
    struct Link_Node * next;
}Link_Node, *Linked_Elem;

void make_node(Linked_Elem *node, int val)
{
    *node=(Linked_Elem)malloc(sizeof(Link_Node));
    (*node)->value=val;
    (*node)->next=NULL;
}

void build_linked_list(Linked_Elem *list, int val)
{
    Linked_Elem p;
    Linked_Elem new_ptr;

    make_node(&new_ptr, val);

    if(*list==NULL)
    {
        *list=new_ptr; 
    }
    else
    {
        p = *list;

        while (p->next != NULL)
        {
            p = p->next;
        }

        p->next = new_ptr;
    }

    return;
}

2.2 递归算法

首先介绍简洁而优雅的递归算法,递归算法秉承”大事化小,小事化了“的算法理念,最终把问题分而治之,递归的关键是找到子问题,那么寻找线性表反转的子问题就成为解决问题的核心与关键。递归的子问题可以通过迭代,不断缩小线性链表的元素规模。

通过不断向后移动线性表中的元素位置,达到缩小线性表规模的目的。当子问题中仅包含单个元素或原问题本身为空集,此时就构成递归算法的base返回基础的情况。

线性链表 反转 -(递归与非递归算法)_20230420

当问题规模缩小满足递归出口条件时候,函数就进入出栈操作流程。

递归入栈过程,

线性链表 反转 -(递归与非递归算法)_20230420

递归出栈过程,

递归的出栈后,实际上仅包含两个操作语句,首先是head->next->next=head,此时对head的next域的next域进行赋值,赋值到其本身,它形成一个环,然后利用语句head->next=NULL, 隔断环的结构。随着不断出栈,那么就形成了从后一元素指向前一元素的线性链表。

线性链表 反转 -(递归与非递归算法)_20230420

递归过程的难点之一是如何保存反转后链表的头指针,这就需要用到递归扩展(propagation)的基本概念,简单做法就是,在第一次出栈之前,逐步递归返回第一次出栈的元素,也即是相同的首元素不断出栈,不断把值传递给下一个栈,通过return 不断返回当前栈里面指针,给到下一个栈。

线性链表 反转 -(递归与非递归算法)_20230420

具体的代码实现,

Linked_Elem reverse_linked_list_recursion(Linked_Elem head)
{
    Linked_Elem p;

    if(head==NULL || head->next==NULL)
    {
        return head; //keep head by each frame stack
    }
    else
    {
        p=reverse_linked_list_recursion(head->next); //keep returned pointer
        head->next->next=head;//operation on the parameters of function
        head->next=NULL;//operation on the parameters of function
        return p; //return head by each frame stack
    }
}

2.3 迭代方法

迭代方法采用从线性表头至尾部的的遍历,其本质是对两个结点之间的连接关系进行反转,从最简单的两个元素线性表分析,我们可以看到,只需要把后一个线性表的next指针指向前一个结点,前一个结点的next指针域置空后就满足反转的要求。

线性链表 反转 -(递归与非递归算法)_20230420

如果线性链表中的元素超过两个,那么问题就来了,邻接元素的next域指向前一个元素之后,就无法再遍历后续的元素。这时候滚动数组的概念应运而生。

具体看实际例子,设定指针start, end 和temp, 每次对start 和end的指针关系进行倒置,同时用temp指针保存倒置之前的end下一个结点,然后这三个结点指针整体往前移动1位,重复上述操作。

线性链表 反转 -(递归与非递归算法)_20230420

线性链表 反转 -(递归与非递归算法)_20230420

线性链表 反转 -(递归与非递归算法)_20230420

代码实现

Linked_Elem reverse_linked_list_iteration(Linked_Elem head)
{
    Linked_Elem start;
    Linked_Elem end;
    Linked_Elem temp;

    start=head;
    end=start->next;
    start->next=NULL;

    while(end)
    {
        temp=end->next;
        end->next=start;
        start=end;
        end=temp;        
    }

    return start;
}

2.3 头部插入法

头插法和尾插法实际上是建立线性链表的两种常规的方式,由于题目要求倒置,所以需要从头到尾在线性遍历的同时采用头部插入法,如果采用尾插法,那么就相当于复制一个相同的线性表。

头部插入法的具体实现为,建立一个临时头部结点,同时开始遍历原线性链表,先遍历后插入,最后返回临时头部结点的next域。

线性链表 反转 -(递归与非递归算法)_20230420

线性链表 反转 -(递归与非递归算法)_20230420

线性链表 反转 -(递归与非递归算法)_20230420

代码实现

Linked_Elem reverse_linked_list_head_insertion(Linked_Elem head)
{
    Linked_Elem temp_head;
    Linked_Elem p;
    Linked_Elem q;

    temp_head=(Linked_Elem)malloc(sizeof(Link_Node));
    temp_head->next=NULL;
    p=head;

    while(p)
    {
        q=p->next;
        p->next=temp_head->next;
        temp_head->next=p;
        p=q;
    }

    return temp_head->next;
    
}

2.4 原线性表就地反转法(in-place reversal)

对原有线性表进行反转,无需建立额外线性表,反转完成后,原来线性表当中的自动形成一个线性反转链表。这个方法的巧妙之处在于,它通过参数中的head指针,以及额外的start和end指针就可以实现就地反转,可以形象称之为“就地翻筋斗”。

以具体实现流程介绍(部分),它实际上先隔离end结点,用start->next指针进行保存,实际上start->next指针在程序执行过程中它的位置保持不变,主要作用是记录下一个待处理的结点。end->next=head表明,重新进行反转链接的操作,而后更新head的位置,指向新的end, 最后把end移动到新的待处理的结点,这时候一个循环周期完成,直至迭代直至所有结点遍历结束。

线性链表 反转 -(递归与非递归算法)_20230420

线性链表 反转 -(递归与非递归算法)_20230420

代码实现

Linked_Elem reverse_linked_list_in_place(Linked_Elem head)
{
    //It is hard in understanding the reverse in place
    Linked_Elem start;
    Linked_Elem end;

    start=head;
    end=start->next;

    while(end)
    {
        start->next=end->next; // Isolate the end and keep its next in start's next
        end->next=head; //link end with old head
        head=end;  // move old head to new head(end pointer)
        end=start->next; // move end to next to be processed target
    }

    return head;
}

  1. 小结

通过线性链表反转练习,复习了线性链表的基本结构,同时通过递归和非递归算法的对比,体现出递归模式的优雅和代码的简洁,本次递归过程中学习了返回值的propagation 模式,这种模式就是通过栈接力,直至把最初的值传递给最后出栈的函数。

参考资料:

《数据结构》清华大学,严蔚敏文章来源地址https://www.toymoban.com/news/detail-423164.html

到了这里,关于线性链表 反转 -(递归与非递归算法)_20230420的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉树的遍历(先序遍历,中序遍历,后序遍历)递归与非递归算法

    先序遍历:先遍历一颗树的根节点,后遍历左子树,最后遍历右子树     先序遍历序列: 1 - 2 - 4 - 5 - 3 - 6 - 7 分解子问题方法 思路:将一颗二叉树看做两个部分,一个部分是左路节点,另一个部分是左路节点的右子树,先将二叉树的左路节点全部入栈,再依次出栈,出栈的

    2024年02月14日
    浏览(41)
  • 数据结构与算法学习:二叉树的后序遍历的递归与非递归实现,以及非递归实现中的流程控制的说明。

    需求二叉树: 采用二叉树后序遍历非递归算法。设置一个指针p初始指向树根,p先入栈,而后使得p指向它的左孩子p-firstchild,重复操作,使得每个左孩子都依次入栈,同时初始化一个Treenode*类型的指针 pre,这个指针是后序前驱,这个后序前驱用以区分为已访问过的结点和未

    2023年04月22日
    浏览(49)
  • 算法-设计链表、移除链表元素、反转链表

    伪装成一个老手! 设计一个单链表,其中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。 实现 MyLinkedList 类: MyLinkedList()初始化 MyLinkedList 对象。 int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1

    2024年02月11日
    浏览(97)
  • 【算法】链表反转

    给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。 数据范围: 要求:空间复杂度 ,时间复杂度 。 如当输入链表{1,2,3}时, 经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。 每次反转需要修改两个

    2024年02月12日
    浏览(40)
  • 【算法手记03】反转链表

    反转链表很重要,是链表题中的高频考点,部分题目可能还需要将反转链表抽出来作为一个函数使用。这几种方式都必须熟练手搓。 lc206.给定单链表头结点,给出反转后的链表。 反转后的新链表带一个dummy结点,将原链表的结点依次插入dummy结点之后,即可完成反转。过程大

    2024年02月19日
    浏览(31)
  • Java反转链表,简单算法

    Java 单向链表,指的是一种数据结构,用于存储一系列的元素。每个元素包含两部分:一个存储数据的值和一个指向下一个元素的引用。 单向链表由多个节点组成,每个节点都包含一个数据元素和一个指向下一个节点的引用。 链表的起始节点称为头节点,尾节点的引用为空(

    2024年01月17日
    浏览(36)
  • 第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    1、前序、中序、后序遍历 分析: 完全二叉树: 叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧 2、线性结构 3、其它 4、单向链表构建 (1)定义一个单向链表SingleLinked类 包含私有的静态内部类Node 包含Object类型的data属性和Node类型的next属性 包含

    2024年01月23日
    浏览(50)
  • 【数据结构和算法】反转链表

    Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 方法一:迭代(双指针) 2.2 方法二:递归 三、代码 3.1 方法一:迭代(双指针) 3.2 方法二:递归 四、复杂度分析 4.1 方法一:迭代

    2024年01月18日
    浏览(53)
  • 【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:算法百炼成神 本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面

    2024年02月17日
    浏览(60)
  • 算法通关村第二关——链表反转

    链表反转,就是链表原来是1-2-3-4-5,经过反转处理过后变成5-4-3-2-1 处理链表反转,有两种方式,一个是建立虚拟头结点,一个是直接操作链表反转。  这是执行的流程 最核心的两行就是 直接想我要让她反转,我现在设立了虚拟头结点,那我就要让新加进这个反转链表的结点

    2024年02月13日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包