判断一个链表是否为回文序列

问题重述：

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

示例 1：

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

示例 2：

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

提示：

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

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

问题分析：

这道题一看到，一般的想法就是使用栈来解决，栈的性质是先入后出，我们将所有的元素压入栈中，从栈顶到栈底的元素顺序和链表的顺序刚好相反，如果链表为回文序列，那么从栈顶元素开始到栈底和链表从头到尾的元素值是相同的

对上一个方法的优化是仅仅将链表的一半元素加入栈中，然后进行对比，可以节省一半的时间（使用双指针来得到一般的元素）

进阶解法就是不使用栈，直接将链表的右边元素反转，然后直接和链表左边元素进行比较（因为此时左边链表和右边链表都指向中间节点，只需要依次进行比较就可以得到结果）

解法：

栈，栈+双指针，链表反转

解题：

代码：

解法一：暴力解法

public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack();
        ListNode node = head;
        while(node != null){
            stack.push(node.val);
            node = node.next;
        }
        while(!stack.isEmpty() && head != null){
            if(stack.peek() == head.val){
                head = head.next;
                stack.pop();
            }else{
                break;
            }
        }
         if(stack.isEmpty()){
                return true;
            }else {
                return false;
            }
    }

解析：就是暴力解法，将链表所有元素加入到栈中，然后从栈中弹出一个一个元素和链表的值进行比较（只需要对栈的性质熟悉，很容易就可以做出来）

解法一的优化：

public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        // 使用双指针找到中间节点
        ListNode cur = head;
        ListNode right = head;
        while(cur.next != null && cur.next.next != null){
            right = right.next;
            cur = cur.next.next;
        }
        // 此时的right指向的是中间结点（如果长度是偶数对应的就是两个中间节点的前一个结点）
        Stack<ListNode> stack = new Stack();
        right = right.next;
        while(right != null){
            stack.push(right);
            right = right.next;
        }
        // 此时栈内存放的是链表的右半边结点，栈顶到栈底依次是链表的尾部
        while(!stack.isEmpty()){
            if(stack.pop().val != head.val){
                return false;
            }
            head = head.next;
        }
        return true;
    }

解析：相较暴力解法，这个方法的区别就是使用双指针

进阶：

 public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        // 使用双指针找到中间节点
        ListNode cur = head;
        ListNode right = head;
        while(cur.next != null && cur.next.next != null){
            right = right.next;
            cur = cur.next.next;
        }
        // 接下来将右边的链表反转
        cur = right.next;
        // 这一步是为了后面进行比较
        right.next = null;
        ListNode next = null;
        while(cur != null){
            next = cur.next;
            cur.next = right;
            right = cur;
            cur = next;
        }
        // 此时的head和cur对应的分别为头和尾，直接进行比较即可,right对应的是最后一个结点
        boolean flag = true;
        cur = right;
        next = head;
        while(next != null && cur != null){
            if(next.val != cur.val){
                flag = false;
                break;
            }
            next = next.next;
            cur = cur.next;
        }
        // 需要将链表恢复原状，然后返回flag（题目如果没要求也可以不恢复）
        cur = right.next;
        right.next = null;
        while(cur != null){
            next = cur.next;
            cur.next = right;
            right = cur;
            cur = next;
        }
        return flag;
    }

解析：这道题的思路首先创建两个几点，作为指针找到链表的中间节点（快慢指针，一个移动一格一个移动两个），当快指针移动到链表的尾部的时候，慢指针刚好移动到链表的中间位置，如果链表长度为偶数，那么慢指针的位置会是两个中间节点的前一个结点。找到了中间节点后，使用一个while循环来将右边的部分链表反转，想要实现反转我们需要获取当前结点以及当前节点的前一个结点和后一个结点，通过这些才能够实现。（需要注意的是在循环之前，需要将中间节点的next设置为null，因为如果不设置为null，会导致后面进行比较时陷入无限循环）当后面的链表被反转后，此时左半部分和右半部分的链表共同指向中间节点，我们此时的right存放着最右边的结点（也可以说是右边链表的起点），此时我们从左右两边链表的起点开始，依次进行比较，如果相同则比较下一个元素，如果不同则将标志设置为false，最后循环完成后，我们已经实现了对链表的判断，（但是这个时候的链表结构是有问题的，如果需要我们可以将链表恢复）

总结：

对于回文序列的判断，最简单粗暴的就是使用栈，也可以使用数组来实现，将头和尾进行比较就可以，如果是字符穿或者数字的话，直接将其分割开来放在栈中或者数组中就可以。