【Leetcode】234. Palindrome Linked List（BN的递归）（判断回文链表）

我不是女神ヾ 2022-01-21 23:09 147阅读 0赞

Given a singly linked list, determine if it is a palindrome.

**Example 1:**

Input: 1->2
    Output: false

**Example 2:**

Input: 1->2->2->1
    Output: true

**Follow up:**  
Could you do it in O(n) time and O(1) space?

题目大意：

判断链表是否是回文。尝试在O(n) time和O(1) space条件下解决。

解题思路：

肯定使用递归，但是递归时只能回溯到上一个节点，而从头结点向下同时遍历无法在在递归内完成，所以需要借助外部变量，当每一次回溯时移动到下一位。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    private:
        ListNode* _node;
        bool helper(ListNode* tmp){
            if(tmp == nullptr)
                return true;
            auto ans = helper(tmp->next) && (tmp->val == _node->val);
            _node = _node->next;
            return ans;
        }
    public:
        bool isPalindrome(ListNode* head) {
            if(head == nullptr || head->next==nullptr)
                return true;
            _node = head;
            return helper(head);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode234--回文链表

请判断一个链表是否为回文链表。进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？解法一： / Definition f

待我称王封你为后i/ 2022年11月17日 05:14/ 0 赞/ 149 阅读

相关 LeetCode 234. 回文链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

朴灿烈づ我的快乐病毒、/ 2022年11月01日 04:26/ 0 赞/ 187 阅读

相关 234. Palindrome Linked List （回文链表判断）

Given a singly linked list, determine if it is a palindrome. Follow up: Could you d

深藏阁楼爱情的钟/ 2022年07月15日 01:26/ 0 赞/ 169 阅读

相关 leetcode 234. Palindrome Linked List 回文链表的判断 + 双指针

Given a singly linked list, determine if it is a palindrome. Follow up: Could you do

短命女/ 2022年06月08日 12:15/ 0 赞/ 120 阅读

相关 LeetCode234. 回文链表

请判断一个链表是否为回文链表。示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: tr

た入场券/ 2022年05月23日 03:48/ 0 赞/ 174 阅读

相关【LeetCode】234. 回文链表

题目链接：[https://leetcode-cn.com/problems/palindrome-linked-list/description/][https_leetco

痛定思痛。/ 2022年05月11日 11:22/ 0 赞/ 157 阅读

相关 LeetCode：234. Palindrome Linked List（判断一个链表是不是回文链表）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

我会带着你远行/ 2022年04月11日 12:08/ 0 赞/ 152 阅读

相关【Leetcode】234. Palindrome Linked List（BN的递归）（判断回文链表）

Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1->

我不是女神ヾ/ 2022年01月21日 23:09/ 0 赞/ 148 阅读

相关 leetcode 234 回文链表 Palindrome Linked List

![1588437-20190227214511956-2063467543.png][] 要求用O(n)时间，和O(1)空间，因此思路是用本身链表进行判断，既然考虑回文，本

浅浅的花香味﹌/ 2021年12月21日 01:17/ 0 赞/ 220 阅读

相关 LeetCode：234. Palindrome Linked List 回文链表

试题： Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1

野性酷女/ 2021年06月24日 16:11/ 0 赞/ 334 阅读