LeetCode 234 Palindrome Linked List

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

题目分析

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/#二优化空间复杂度

大致思路:

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/