題目：對于一個鏈表，請設(shè)計一個時間復(fù)雜度為O(n),額外空間復(fù)雜度為O(1)的算法，判斷其是否為回文結(jié)構(gòu)。

• 給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結(jié)構(gòu)。保證鏈表長度小于等于900。
• 測試樣例：1->2->2->1
• 返回：true

方法1：
空間O(n)整個鏈表遍歷兩邊， 開一個棧，第一遍遍歷把鏈表中每個元素push進(jìn)棧中，
這樣堆中的元素的pop順序就是鏈表的倒序輸出；第二遍就開始pop棧中數(shù)據(jù)，每pop一個數(shù)據(jù)，
就把這個數(shù)據(jù)跟鏈表中進(jìn)行對比，如果相同繼續(xù)往下走，如果不同返回false。
此種情況下，時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。

/**
     * 思路1：空間O(n)整個鏈表遍歷兩邊， 開一個棧，第一遍遍歷把鏈表中每個元素push進(jìn)棧中，
     * 這樣堆中的元素的pop順序就是鏈表的倒序輸出；第二遍就開始pop棧中數(shù)據(jù)，每pop一個數(shù)據(jù)，
     * 就把這個數(shù)據(jù)跟鏈表中進(jìn)行對比，如果相同繼續(xù)往下走，如果不同返回false。
     * 此種情況下，時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。
     * @param head
     * @return
     */
    public static boolean chkPalindrome1(Node head) {
        Stack<Node> stack = new Stack<>();
        Node headTemp = head;
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        while (headTemp != null && !stack.empty()) {
            if (headTemp.value == stack.pop().value) {
                headTemp = headTemp.next;
            } else {
                return false;
            }
        }
        return true;
    }

方法2：
分別正序和逆序拼接節(jié)點值字符串， 比較字符串是否相同
時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)

 /**
     * 分別正序和逆序拼接節(jié)點值字符串， 比較字符串是否相同
     * 時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)
     * @param head
     * @return
     */
    public static boolean chkPalindrome2(Node head) {
        String str1 = ""; //正序拼接
        String str2 = ""; //逆序拼接

        while (head != null) {
            str1  = str1 + head.value;
            str2 = head.value + str2;
            head = head.next;
        }
        if(str1.equals(str2) && str1.length() > 1){
            return true;
        }
        return false;

    }

方法3：
1 找到鏈表中點，
2 翻轉(zhuǎn)右半部分，
3 從兩個鏈表頭開始判斷節(jié)點值相同。
4 然后再將右側(cè)鏈表翻轉(zhuǎn)回來
復(fù)雜度: 時間O(n), 空間O(1)

/**
     * 1 找到鏈表中點，
     * 2 翻轉(zhuǎn)右半部分，
     * 3 從兩個鏈表頭開始判斷節(jié)點值相同。
     * 4 然后再將右側(cè)鏈表翻轉(zhuǎn)回來
     *
     * 復(fù)雜度
     * 時間O(n) 空間O(1)
     *
     * @param head
     * @return
     */
    public static boolean chkPalindrome3(Node head) {
        //找到中點
        Node mid=head;//中點
        Node fast=head;
        while(fast.next!=null&&fast.next.next!=null) {//奇偶長度情況
            fast=fast.next.next;
            mid=mid.next;
        }

        //翻轉(zhuǎn)右側(cè)鏈表
        Node cur=mid.next;//
        mid.next=null;
        Node behind = null;
        Node before = mid;//右側(cè)翻轉(zhuǎn)后尾節(jié)點指向中間節(jié)點，中間節(jié)點為左右兩個鏈表的共同尾節(jié)點
        while(cur!=null) {
            behind=cur.next;
            cur.next=before;
            before=cur;
            cur=behind;
        }
        Node rHead=before;

        //檢查是否是回文的
        Node lNode=head;
        Node rNode=before;//
        boolean res=true;
        while(lNode!=null && rNode!=null) {//原鏈奇偶長度都o(jì)k, 某一半最早到null，就結(jié)束比較了
            System.out.println("左：" + lNode.value + ", 右： " + rNode.value);
            if(lNode.value!= rNode.value) {
                res=false;
                break;
            }
            lNode=lNode.next;
            rNode=rNode.next;
        }

        //右側(cè)鏈表翻轉(zhuǎn)回去
        before=rHead;
        cur=rHead.next;
        behind=null;
        while(cur!=null) {
            behind=cur.next;
            cur.next=before;
            before=cur;
            cur=behind;
        }

        return res;
    }

測試：

 public static void main(String[] args) {
        Node n1=new Node(1);
        Node n2=new Node(2);
        Node n3=new Node(3);
        Node n4=new Node(3);
        Node n5=new Node(2);
        Node n6=new Node(1);

        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        n5.next=n6;
        Node head=n1;

        boolean result= chkPalindrome3(head);
        System.out.println(result);
    }