LeetCode234回文链表

题目链接

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

题解一

• 将链表元素存入数组，然后从首尾遍历
• 注意如果是空链表，结果也是true

// Problem: LeetCode 234
// URL: https://leetcode-cn.com/problems/palindrome-linked-list/
// Tags: Linked List Two Pointers Recursion
// Difficulty: Easy

#include <iostream>
#include <vector>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
};

class Solution{
public:
    bool isPalindrome(ListNode* head) {
        // 存储链表中的结点
        vector<int> vals;
        while(head != nullptr){
            vals.push_back(head->val);
            head = head->next;
        }
        // 从首尾两侧遍历
        int front = 0, back = vals.size()-1;
        while(front < back){
            if(vals[front] != vals[back])
                return false;
            front++;
            back--;
        }
        return true;
    }
};

题解二

• 递归写法，有点牛的

// Problem: LeetCode 234
// URL: https://leetcode-cn.com/problems/palindrome-linked-list/
// Tags: Linked List Two Pointers Recursion
// Difficulty: Easy

struct ListNode{
    int val;
    ListNode* next;
};

class Solution{
private:
    ListNode* front;
    
    bool check(ListNode* node){
        if(node != nullptr){
            // 先检查尾部
            if(!check(node->next)) return false;
            // 检查当前结点
            if(node->val != this->front->val) return false;
            // 该结点检查完了，递归使node从后往前，手动从前往后更新front
            this->front = this->front->next;
        }
        return true;
    }

public:
    bool isPalindrome(ListNode* head) {
        this->front = head;
        return this->check(head);
    }
};

---

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

---