LeetCode 234 Palindrome Linked List

    
        标签：
        
            链表问题
        
            LeetCode
        
    发布于：2022-02-05 22:59:18
    编辑于：2022-02-05 23:21:17
    浏览量：1027

题目分析

https://leetcode.com/problems/palindrome-linked-list/

暴力法

遍历一遍链表，构造对应的字符串，然后再判断字符串是否是回文字符串。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> list;
        while (head) {
            list.push_back(head->val);
            head = head->next;
        }
        for (int i = 0; i < list.size() / 2; i++) {
            if (list[i] != list[list.size() - 1 - i]) return false;
        }
        return true;
    }
};

递归法（后续遍历链表）

https://labuladong.gitee.io/algo/2/17/19/

太 6 了，仿照二叉树的前中后序遍历，这里也可以后续遍历链表：

class Solution {
public:
    ListNode* left;
    bool isPalindrome(ListNode* head) {
        left = head;
        return travel(head);
    }
    
    bool travel(ListNode* right) {
        if (!right) return true;
        auto ok = travel(right->next);
        if (!ok) return false;
        if (right->val != left->val) return false;
        left = left->next;
        return true;
    }
};

时间复杂度 O(n)，空间复杂度也是 O(n)，函数调用栈的占用。

空间复杂度 O(1) 的解法

https://labuladong.gitee.io/algo/2/17/19/#二优化空间复杂度

大致思路：

利用快慢指针找到中点；
翻转中点之后的链表；
再遍历对比即可。

Links: leetcode-234-palindrome-linked-list