链表的回文

请编写一个函数，检查链表是否为回文。
给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。

测试样例：
{1,2,3,2,1} 返回：true
{1,2,3,2,3} 返回：false

思路:

1. 遍历两遍链表,第一遍利用栈保存所有节点,第二遍遍历时依次弹出栈中元素进行比较.时间复杂度是O(n),空间复杂度是O(n).
2. 利用栈保存链表左半部分的节点, 然后在遍历链表右半部分时依次弹出栈中的元素去和后面的节点依次进行比较. 该方法的时间复杂度是O(n),空间复杂度是O(n/2).
3. 类似方法2,利用floyd判圈算法(快慢指针法)找到中间节点.然后反转右边的链表.然后两条链表同时遍历进行比较.比较结束后再将右侧的链表复原,连回左侧的链表.

方法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;
    }
}