专栏首页架构说漫谈递归-回文链表

漫谈递归-回文链表

题目

234. 回文链表 请判断一个链表是否为回文链表。

测试

示例 1: 输入: 1->2 输出: false

示例 2: 输入: 1->2->2->1 输出: true

答案

/**
1  定义2个指针,head tail 
2. 递归遍历tail链表
3. 通过
     head++  链表前进, 递归特点:从上到下 
             这个是子递归完在函数内部修改的,然后当前递归在使用
             head已经发生改变)
     tail --     链表倒退,  
                 递归特点 回溯,利用函数栈跟踪轨获取最后节点。
                 tail没有改变
   判断是否回文 tail ==head
4.如果是继续,如果不是返回false
//执行用时: 20 ms, 在Palindrome Linked List的C++提交中击败了42.09% 的用户
**/
class Solution {
public:
    bool isPalindrome(ListNode* head) {
         //这2个参数意义不一样一个指针,一个指针的引用
        return isPalindrome(head,head);
    }
  
    bool isPalindrome(ListNode* tail,ListNode* &head)
    {
        if(NULL==tail) 
        {
            return true;
        }       
         //从上到下不做任何原始比较,直到结束。返回true
        bool flag=isPalindrome(tail->next,head);
        if (false ==flag)
        {
            return false;

        }        //最外层比较
        if (tail->val !=head->val)
        {
            return false;
        }
        //最里层比较,head是引用,修改的指针本身
        head =head->next;
        return flag;

    }
};

分析

  1. 什么是回文:
  1. 这就是递归 recursion(head)
  2. 链表 每个节点都是相同的结构 符合递归的特点 链表顺序遍历,这个规律无法违背?
  3. 递归特点之一 回溯 实现链表倒序遍历

性能

因为采用递归

执行用时: 20 ms, 在Palindrome Linked List的C++提交中击败了42.09% 的用户

空间: o(n) 时间:o(n)

本文分享自微信公众号 - 架构说(JiaGouS)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-30

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫谈递归-链表合并

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    程序员小王
  • 频繁分配释放内存导致的性能问题的分析

    1 压力测试过程中,发现被测对象性能不够理想,具体表现为: 进程的系统态CPU消耗20,用户态CPU消耗10,系统idle大约70 2 用...

    程序员小王
  • 平安证券Kubernetes容器集群的DevOps实践

    在前面众多微信的分享系列中,对k8s的体系构成,各个概念的定义,各组件的作用等都已介绍多次,此处就不再重复这些内容。在这篇文章中,主要和大家分享一些我们平安证券...

    程序员小王
  • 算法模板——平衡树Treap

    实现功能如下——1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个) 3. 查询x数的排名(若有多个相同的数,因输出最小的排名) 4. 查询排名为x...

    HansBug
  • 3224: Tyvj 1728 普通平衡树

    3224: Tyvj 1728 普通平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2566  Sol...

    HansBug
  • LeetCode 61. Rotate List

    ShenduCC
  • 《剑指offer》第22天:链表成环的新解法

    思路:通过hash表来检测节点之前是否被访问过,来判断链表是否成环。这是最容易想到的一种题解了。过于简单,直接上代码,go:

    程序员小浩
  • python算法与数据结构-栈(43)

      栈作为一种数据结构,是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹...

    Se7eN_HOU
  • RBR:2017年全球最有影响力的50家机器人公司

    选自Robotics Business Review 机器之心编译 参与:微胖,李亚洲,蒋思源 美国《机器人商业评论》(Robotics Business Re...

    机器之心
  • 二叉树的常用算法递归2 非递归3 小结4 实战coding5序列化和反序列化判断一棵二叉树是否是平衡二叉树判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

    JavaEdge

扫码关注云+社区

领取腾讯云代金券