image.png

解法

递归解法，练下递归当堆栈使用，先操作链表最后一个元素的解法。

/**
 * 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 {
    ListNode pre;
    public boolean isPalindrome(ListNode head) {
        pre = head;               
        return dfs(head);
    }

    /**
     * 递归当堆栈使用，判断和正序遍历是否一致
     */
    public boolean dfs(ListNode node) {
        if (node != null) {
            if (!dfs(node.next)) {
                return false;
            }
            // 递归执行时，会先将当前逻辑放进堆栈帧，
            // 执行到最后元素时，才会执行到这里
            if (node.val != pre.val) {
                return false;
            }
            pre = pre.next;
            return true;
        }
        return true;
    }
}

后半部分链表进行链表反转，整个包含快慢指针和链表反转，空间复杂度为O(1)。

/**
 * 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 {
    
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 快慢指针找链表中间点
        ListNode midNode = getMidNode(head);
        // 反转中间点后面的链表
        ListNode reverseNode = reverseListNode(midNode);
        while (head != null && reverseNode != null) {
            if (head.val != reverseNode.val) {
                return false;
            }
            head = head.next;
            reverseNode = reverseNode.next;
        }
        return true;
    }

    private ListNode reverseListNode(ListNode node) {
        System.out.println(node.val);
        ListNode pre = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

    private ListNode getMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // fast为空，是偶数情况下，slow就是后半个链表的第一个节点
        // fast不为空，是奇数情况下，slow是中间点，往后移一位才是第一个节点
        return fast == null ? slow : slow.next;
    }
}