使用 oh-my-zsh

给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。

示例 1：

1 -> 2 -> 2 -> 1 -> null

输入：head = [1,2,2,1]
输出：true

示例 2：

1 -> 2 -> null

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

提示：

• 链表中节点数目在范围[1, 105] 内
• $0 <= Node.val <= 9$

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

分析

• 利用数组存储链表节点，进行回文遍历比对
• 求链表长度，利用栈，存储前半部分，然后出栈依次和后半部分比较，不一致，则返回false
• 递归，维护一个全局变量，引用前一个节点

利用数组存储链表节点，进行回文遍历比对

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}

递归方法

• currentNode 非空节点，先递归尾部
  • 不是回文直接返回false
• 头尾依次对比
  • 不是回文直接返回false
• 更新节点frontPointer，ps: currentNode 递归更新
• 返回true

class Solution {
    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            // 先递归尾部
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            // 头尾依次对比
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            // 更新头，因为尾部递归了
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;// 记录frontPointer
        return recursivelyCheck(head);
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com