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

我不是女神ヾ 2022-01-21 23:09 165阅读 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 条评论，165人围观）

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

相关阅读

相关 234. Palindrome Linked List（回文链表+O(1)空间）

这一题在leetcode中有些许争议，认为题目的描述有问题，因为说了用O（N）时间复杂度和O（1）空间复杂度。点在这个1的空间复杂度。我倾向于认为这个O（1）空间复杂度是指不再

柔情只为你懂/ 2023年07月23日 12:53/ 0 赞/ 9 阅读

相关 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 赞/ 177 阅读

相关 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 赞/ 135 阅读

相关 LeetCode234. 回文链表

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

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

相关 LeetCode【234.回文链表】

题目描述 > 请判断一个链表是否为回文链表。示例 1 输入： 1 − > 2 1->2 1−>2 输出： f a l s e false false

r囧r小猫/ 2022年05月08日 12:18/ 0 赞/ 196 阅读

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

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

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

相关【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 赞/ 166 阅读

相关 leetcode 234 回文链表 Palindrome Linked List

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

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

相关 LeetCode 234. 回文链表

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

绝地灬酷狼/ 2021年09月27日 00:18/ 0 赞/ 288 阅读

相关 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 赞/ 346 阅读