LeetCode 234.回文链表（Java）

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

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode cur = head;  //接收链表
        Stack stack = new Stack(); //创建一个栈来接收链表中每个节点的值
        while(cur != null) {  //取链表值，栈先进后出，顺序存入，逆序输出
            stack.push(cur.val);  //入栈
            cur = cur.next;  //指针后移
        }
        while(head != null) {  //逆序输出栈中元素，与链表中元素进行对比，如果有不相等则不是回文数
            int res = stack.pop();  //出栈
            if(res != head.val) {
                return false;
            }
            head = head.next;  //指针后移
        }
        return true;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) { 
            return true;
        }
        ListNode cur = head;  //接收链表
        ListNode p1 = head;  //快指针
        ListNode p2 = head;  //慢指针
        Stack stack = new Stack(); //创建一个栈来接收链表中每个节点的值
        while(p1.next != null && p1.next.next != null) {  //移动指针
            p1 = p1.next.next;
            p2 = p2.next;
        }
        p2 = p2.next;
        while(p2 != null) {  //取链表值，栈先进后出，顺序存入，逆序输出
            stack.push(p2.val);  //入栈
            p2 = p2.next;
        }

        while(!stack.empty()) {  //逆序输出栈中元素，与链表中元素进行对比，如果有不相等则不是回文数
            int res = stack.pop();  //出栈
            if(res != head.val) {
                return false;
            }
            head = head.next;  //指针后移
        }
        return true;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) { 
            return true;
        }
        ListNode cur = head;  //接收链表
        ListNode p1 = head;  //快指针
        ListNode p2 = head;  //慢指针
        ListNode prev = null;  //保存逆序链表
        while(p1.next != null && p1.next.next != null) {  //移动指针
            p1 = p1.next.next;
            p2 = p2.next;
        }
        p2 = p2.next;
        while(p2 != null) {  //将后半段链表反转
            ListNode nextTemp = p2.next;
            p2.next = prev;
            prev = p2;
            p2 = nextTemp;
        }
        while(prev != null) {  //遍历反转链表
            if(prev.val != cur.val) {
                return false;
            }
            prev = prev.next;
            cur = cur.next;
        }
        return true;


    }
}