チェーンテーブルが返信チェーンテーブルであるかどうかを判断する

第1の方法:余分な空間複雑度O(N)、チェーンテーブルを遍歴する時、要素をスタックに入れて、再び遍歴する時、スタックの中から要素を弾き出して、両者の大きさを比較して、回文チェーンテーブルの第2の方法かどうかを判断することができます:速いポインタを利用して、まずチェーンテーブルの中間位置を見つけて、それからチェーンテーブルの後半部分を反転して、それからそれぞれチェーンテーブルの両端から比較的な大きさを遍歴して、最後にチェーンテーブルを元の構造に復元

public class PalindromeLinkedList {

    
    public static void main(String[] args) {
        
        Node head = new Node(1);
        head.next = new Node(3);
        head.next.next = new Node(5);
        head.next.next.next = new Node(5);
        head.next.next.next.next  = new Node(3);
        head.next.next.next.next.next  = new Node(1);
        
        display(head);
        
        //        ，        ，     ，         ，slow       ，         ，slow       （  ）    
        Node fast = head;
        Node slow = head;
        while(fast.next != null && fast.next.next != null){
             fast = fast.next.next;
             slow = slow.next;
        }
        //   slow       ，  slow   
        Node middle = slow;
        
        //              
        Node help = slow.next;
        //      null
        slow.next = null;
        
        // help        
        Node pre = null;
        Node next = null;
        //     ，pre        
        while(help != null) {
            next = help.next;
            help.next = pre;
            pre = help;
            help = next;
        }
        
        //       
        boolean flag = true;
        Node  first = head;
        Node  second = pre;
        while(first != null && second != null) {
            if(first.value != second.value) {
                flag = false;
                break;
            }
           first =  first.next;
           second = second.next;
        }
        System.out.println(flag);
        
        //           
        Node help_restore = pre;
        Node pre_restore = null;
        Node next_restore = null;
        while(help_restore != null) {
            next_restore = help_restore.next;
            help_restore.next = pre_restore;
            pre_restore = help_restore;
            help_restore = next_restore;
        }
        middle.next = pre_restore;
        display(head);
        
    }

    
    public static  void display(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.value + " -> ");
            head = head.next;
        }
        String res = sb.substring(0, sb.lastIndexOf(" -> "));
        System.out.println(res);
    }
    
    public static class Node{
        public int value; // 
        public Node next; //      
 
        public Node(int value) {
            this.value = value;
        }
    }
}