最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 链表天然的递归性

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

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

    对于上面这个链表,其实我们可以这样看待,我们可以想象成是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);
        }
    }
    

    源码下载

    [dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

    导航目录

    [dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(4.3)链表的天然递归结构性质

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 108会员总数(位)
    • 3695资源总数(个)
    • 3本周发布(个)
    • 0 今日发布(个)
    • 181稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级