回文链表

题目描述

  请判断一个链表是否为回文链表

输入输出样例

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

题解

  对于回文数来说，我们可以使用双指针对其进行操作。但是对于这道题目，它的数据结构为链表。如果我们想要像数组那样使用双指针，大概还需要一些其它操作。
  这道题目使用的是链表数据结构，我们首先应该想到的是,它具有递归与迭代的性质。那我们是否可以使用递归或是迭代去获取它的头尾呢，这样问题就变成了一个如何去遍历它的问题。其实大部分遍历思想，我们都可以参考二叉树的三种遍历:前序、中序、后序。
  在这里我们可以使用中序遍历，用right获取链表的尾，用left获取它的头。通过比较判断左右是否相等，从而选出结果。

class Solution {
public:
    ListNode* left;
    bool isPalindrome(ListNode* head) {
        left = head;
        return Palindrome(head);
    }
    bool Palindrome(ListNode* right) {
        if (right == nullptr) return true;
        bool res = Palindrome(right->next);
        res = res && (right->val == left->val);
        left = left->next;
        return res;
    }
};