• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(4.3)链表的天然递归结构性质

极客笔记 Geekerstar 12个月前 (05-13) 465次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

链表天然的递归性

上一节我们对递归这种计算机程序中最重要的逻辑构建的机制进行了一个大概的描述,尤其强调写递归算法的时候要注意这个递归算法的宏观语意,很多时候我们只需要把递归算法理解成一个子过程就好了,其实本身没这么难。

这一小节我们来看看链表与递归有什么关系。

对于上面这个链表,其实我们可以这样看待,我们可以想象成是0这个节点它后面又挂了个链表,而这个链表本身是一个更短的链表,比原始的0,1,2,3,4少了一个节点,这就是之前提过的链表具有天然的递归性。

对于链表来说,我们可以把它理解为一个个节点的挂接,也可以是一个头结点后面又挂接了更短的链表。

对于这个链表来说,1就成了它的头结点,当然我们也可以理解成1后面又挂接了一个更短的链表,其中2是这个新的链表的头结点,依次类推……直到最后我们可以理解为null本身也是一个链表。

有了这些思考,其实链表中很多操作都可以使用递归来完成。

解决链表中删除元素的问题

接下来我们继续使用之前的一个问题把它用递归来完成,这个问题就是删除链表中的元素,但是我们要把链表中所有值为v的元素都删除,怎么使用递归来完成这个任务呢?

之前曾说过设计这个递归函数就要明确递归函数的语意,现在递归函数本身就是在解决这样一个问题,传给这个函数一个链表的头结点和一个元素v,这个函数本身就要将传来的函数中头结点的链表中所有元素为v这样的节点删除,有了这个函数之后,我们就可以这样来解决问题了,

对于最原始的链表,我们可以把它理解成头结点为e这个节点后面跟了一个更短的链表。

现在已经有了一个函数,可以删除链表中更小的指定的元素,假定执行完操作后剩下的链表是这个红色的链表。

剩下的问题就是,怎么通过这个问题的解,构建原问题的解呢?

可以想象一下,对于原问题,其实就是没有考虑头结点的问题,那么我们考虑这个头节点就好了。

如果头节点e不需要删除,最终原问题的结果就是头节点e挂接上子问题求得的这个红色的链表,如果头结点需要把它删除,最终的结果就是我们求出来的这个红色的链。

代码演示

还是上一节链表中删除元素的问题,我们用递归的方式来解决一下

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        if(head == null)
            return head;

        ListNode res = removeElements(head.next, val);
        if(head.val == val)
            return res;
        else{
            head.next = res;
            return head;
        }
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 6, 3, 4, 5, 6};
        ListNode head = new ListNode(nums);
        System.out.println(head);

        ListNode res = (new Solution4()).removeElements(head, 6);
        System.out.println(res);
    }
}

运行一下程序,结果正确

我们还可以把上面的程序简化一下,其实就只有四行代码了

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        if(head == null)
            return head;

        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 6, 3, 4, 5, 6};
        ListNode head = new ListNode(nums);
        System.out.println(head);

        ListNode res = (new Solution5()).removeElements(head, 6);
        System.out.println(res);
    }
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(4.3)链表的天然递归结构性质
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00