[LeetCode234] 判断回文链表（最优空间复杂度解法）

[LeetCode234] 判断回文链表（最优空间复杂度解法）

package com.wangxiaohu;

public class LeetCode234_01 {

    
    boolean isPalindrome(ListNode head) {
        // 快慢指针找到中间节点
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null)
            slow = slow.next;

        // 反转中间节点之后链表
        ListNode left = head;
        ListNode right = reverse(slow);

        // 进行比较
        while (right != null) {
            if (left.val != right.val)
                return false;
            left = left.next;
            right = right.next;
        }
        return true;
    }

    
    ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    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;
        }
    }
}