leetcode 回文链表

题目

给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例1

输入: head = [1,2,3,3,2,1]
输出: true>

示例2

输入: head = [1,2]
输出: false

提示：

链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/aMhZSa
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解思路

• 递归调用，首先判断当前节点是否为空，不为空说明还有节点，遍历后面的节点，一直到最后的节点为空之后，直接返回true
• 返回之后，在if条件语句判断是！true 就是不执行语句，也就是当前的节点是最后的节点，那么继续判断链表表头指针指向的值 是否与当前末尾指针指向的值是否相等，如果不相等，返回false，跳出循环，如果相等，那么链表首指针往后移动，递归返回上一层，也就相当于尾指针往前移动一位。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    ListNode *front_point;
public:
   bool recursivelyCheck(ListNode *currentNode)
   {
       if(currentNode!=nullptr)
       {
           if(!recursivelyCheck(currentNode->next))
           {
               return false;
           }
           if(currentNode->val != front_point->val)
           {
               return false;
           }
           front_point = front_point->next;
       }
       return true;
   }
    bool isPalindrome(ListNode* head) {
        front_point = head;
        return recursivelyCheck(head);
    }
};