[数据结构与算法]三种方法判断链表是否为回文结构

方法一：全部丢到栈中，然后依次取出与链表中的值比较。需要N个额外空间。
方法二：利用快慢指针，找出链表中点位置，将链表后半部分依次压栈，再取出与链表的值比较。需要额外N/2个额外空间。
方法三：利用快慢指针，找出链表中点位置，将链表后半部分翻转，依次比较两链表值，判断是否是回文结构后将翻转的链表还原。

package class04P;

import java.util.Stack;

public class Code04P_IsPalindromeList {

    public static class Node{
        public int val;
        public Node next;
        public Node(int val){
            this.val = val;
        }
    }

    public static boolean IsPalindromeList1(Node head){//head = null时，认为是回文结构
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        while(head != null){
            if(stack.pop().val != head.val) return false;
            head = head.next;
        }

        return true;
    }

    public static boolean IsPalindromeList2(Node head){
        if(head == null || head.next == null) return true;
        Node fast = head, slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = slow.next;

        Stack<Node> stack = new Stack<>();
        while (slow != null){
            stack.push(slow);
            slow = slow.next;
        }
        while(!stack.isEmpty()){
            if(stack.pop().val != head.val) return false;
            head = head.next;
        }

        return true;
    }

    public static boolean IsPalindromeList3(Node head){
        if(head == null || head.next == null) return true;//这里必须要有head.next == null的判断，不然后面单链表的翻转会出现空指针异常

        Node fast = head, slow = head;
        while (fast.next != null && fast.next.next != null){
                slow = slow.next;
                fast = fast.next.next;
        }

        Node tmpHead = slow.next;
        slow.next = null;
        Node pre = slow;
        while (tmpHead != null){
            Node tmpNext = tmpHead.next;
            tmpHead.next = pre;
            pre = tmpHead;
            tmpHead = tmpNext;
        }

        tmpHead = pre;
        slow = head;//这里slow = head只是少申请一个Node
        Boolean res = true;
        while(slow != null){
            if (slow.val != tmpHead.val){
                res = false;
                break;
            }
            slow= slow.next;
            tmpHead = tmpHead.next;
        }

        tmpHead = null;//要是再定义几个Node的话，表述会更加清楚
        while (pre != null) {
            Node tmpNext = pre.next;
            pre.next = tmpHead;
            tmpHead = pre;
            pre = tmpNext;
        }

        return res;
    }

    public static void main(String[] args) {
        Node node1 = new Node(2);
        node1.next = new Node(3);
        node1.next.next = new Node(8);
        node1.next.next.next = new Node(3);
        node1.next.next.next.next = new Node(2);
        System.out.println(IsPalindromeList3(node1));

    }
}