大家好！我是曾续缘❣️
今天是《LeetCode 热题 100》系列
发车第 24 天
链表第 3 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 10⁵] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
难度：❤️

解题方法

递归遍历链表时，先执行递归再进行比较，我们可以做到从后往前读取比较链表的值，这在递归结束后自动移动。

使用全局变量front，我们可以做到从前往后读取链表的值，这需要在比较结束后手动移动。

使用递归和双指针的方法来判断链表是否为回文链表。
设计一个递归函数 recurse(ListNode cur)，递归遍历到链表的末尾，然后在递归返回的过程中，从后往前依次比较链表的节点值。
如果 cur 是 null，说明已经遍历到链表的末尾，返回 true。
如果递归调用 recurse(cur.next) 返回 false，则直接返回 false。
比较 cur.val 和 front.val 的值，如果不等则返回 false。
将 front 更新为它的下一个节点，并返回 true 继续递归。

时间复杂度：O(n)，其中 n 表示链表的长度，需要遍历整个链表来进行比较。

空间复杂度：O(n)，递归调用栈的深度取决于链表的长度。

Code

查看代码

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode front;
    private boolean recurse(ListNode cur){
        if(cur == null){
            return true;
        }
        if(!recurse(cur.next)){
            return false;
        }
        if(cur.val != front.val){
            return false;
        }
        front = front.next;
        return true;
    }
    public boolean isPalindrome(ListNode head) {
        front = head;
        return recurse(head);
    }
}

解题方法 ​

Code ​

解题方法

Code