請(qǐng)編寫一個(gè)函數(shù)，檢查鏈表是否為回文。
給定一個(gè)鏈表ListNode* pHead，請(qǐng)返回一個(gè)bool，代表鏈表是否為回文。

測(cè)試樣例：
{1,2,3,2,1} 返回：true
{1,2,3,2,3} 返回：false

思路:

1. 遍歷兩遍鏈表,第一遍利用棧保存所有節(jié)點(diǎn),第二遍遍歷時(shí)依次彈出棧中元素進(jìn)行比較.時(shí)間復(fù)雜度是O(n),空間復(fù)雜度是O(n).
2. 利用棧保存鏈表左半部分的節(jié)點(diǎn), 然后在遍歷鏈表右半部分時(shí)依次彈出棧中的元素去和后面的節(jié)點(diǎn)依次進(jìn)行比較. 該方法的時(shí)間復(fù)雜度是O(n),空間復(fù)雜度是O(n/2).
3. 類似方法2,利用floyd判圈算法(快慢指針?lè)?找到中間節(jié)點(diǎn).然后反轉(zhuǎn)右邊的鏈表.然后兩條鏈表同時(shí)遍歷進(jìn)行比較.比較結(jié)束后再將右側(cè)的鏈表復(fù)原,連回左側(cè)的鏈表.

方法3代碼

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Palindrome {
    public boolean isPalindrome(ListNode pHead) {
        if(pHead==null||pHead.next==null)return true;
        
        ListNode slow=pHead,fast=pHead;
        while(fast.next!=null&&fast.next.next!=null){ //find mid node
            slow=slow.next;
            fast=fast.next.next;
        }
        
        fast=slow.next; // first node of right list
        slow.next=null; //important 
        ListNode rHead=reverseList(fast); //preserve reversed list's head node
        fast=rHead;     //first node of left list
        slow=pHead;     //first node of right list
        
        boolean isPalindrome=true;
        while(fast.next!=null){
            if(slow.val!=fast.val){
                isPalindrome=false;
                break;
            }
            slow=slow.next;
            fast=fast.next;               
        }
        
        slow.next=reverse(rHead);  //restore reversed list
        return isPalindrome;
    }
    
    /**
    reverse the whole list and return its head node.
    */
    private ListNode reverseList(ListNode head){
        ListNode pre=null,next=null;
        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;           
        }
        return pre;
    }
}