判断一个链表是否为回文结构

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * @描述：判断一个链表是否为回文结构
 * @思路：
 * 1. 将链表的右半区入栈
 * 2.检查栈中的值和顺序是否与未入栈的一致
 * @复杂度：时间O(N)
 * @链接：https://www.nowcoder.com/practice/4b13dff86de64f84ac284e31067b86e2
 */
class Palindrom {


    public static boolean isPalindrom(Node head) {
        //检验
        if(head == null || head.getNext() == null) {
            return false;
        }
        //--找到右半区的头结点
        Node right = head.getNext(); //从第二个结点开始
        Node last = head;
        while (last.getNext() != null && last.getNext().getNext() != null) {
            right = right.getNext();
            last = last.getNext().getNext();
        }
        //--将链表的右半区入栈
        Stack<Integer> stack = new Stack<>();
        while (right != null) {
            stack.push(right.getValue());
            right = right.getNext();
        }
        //--检查栈中的值和顺序是否与未入栈的一致
        Node node = head;
        while (!stack.isEmpty()) {
            if(stack.pop() != node.getValue()){
                return false;
            }
            node = node.getNext();
        }
        return true;
    }

    public static void main(String[] args) {
        Node head = Node.createNodeList(new Integer[]{1, 2, 3, 4, 5});
        System.out.println(Palindrom.isPalindrom(head));
    }


}

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String n = in.readLine();
        String[] items = in.readLine().split(" ");
        Node head = Node.createNodeList(items);
        System.out.println(Palindrom.isPalindrom(head));

    }


}



class Node {

    private Node next;

    private int value;

    public Node(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }


    public static Node createNodeList(Integer[] values) {
        Node head = new Node((values[0]));
        Node node = head;
        for (int i = 1; i < values.length; i++) {
            Node newNode = new Node(values[i]);
            node.next = newNode;
            node = newNode;
        }
        return head;
    }

    public static Node createLoopNodeList(Integer[] values) {
        Node head = new Node((values[0]));
        Node node = head;
        for (int i = 1; i < values.length; i++) {
            Node newNode = new Node(values[i]);
            node.next = newNode;
            node = newNode;
        }
        node.setNext(head);
        return head;
    }

    public static Node createNodeList(String[] values) {
        Node head = new Node(Integer.parseInt(values[0]));
        Node node = head;
        for (int i = 1; i < values.length; i++) {
            Node newNode = new Node(Integer.parseInt(values[i]));
            node.next = newNode;
            node = newNode;
        }
        return head;
    }


    public static void printNodeList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.getValue()).append(" ");
            head = head.getNext();
        }
        System.out.println(sb.toString());
    }

    public static void printLoopNodeList(Node head) {
        if (head == head.getNext()) { //只有一个节点
            System.out.println(head.getValue());
        } else {
            StringBuilder sb = new StringBuilder();
            Node last = head;
            while (last.getNext() != head) {
                sb.append(last.getValue()).append(" ");
                last = last.getNext();
            }
            System.out.println(sb.toString());
        }
    }


}