漫谈递归-回文链表

题目

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) {
        
        return isPalindrome(head,head);
    }
    //bool isPalindrome(ListNode* tail,ListNode* head)
    bool isPalindrome(ListNode* tail,ListNode* &head)
    {
        if(NULL==tail) 
        {
            return true;
        }
        
        bool flag=isPalindrome(tail->next,head);
        if (false ==flag)
        {
            return false;
            
        }
        
        if (tail->val !=head->val)
        {
            return false;
        }
        head =head->next;//
        return flag;
        
    }
};

分析

1. 什么是回文：

   
   image.png
   image.png

image.png

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

性能

因为采用递归

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

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

相关阅读

链表排序