Leetcode 234 Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Solution 1: split by half, reverse 2nd half, can use two pointer to iterate, if find any difference return false.

 public class Solution {  
   public boolean isPalindrome(ListNode head) {  
     if (head==null) return true;  
     ListNode p=head;  
     int n=0;  
     while (p!=null) {  
       p=p.next;  
       n++;  
     }  
     p=head;  
     for (int i=0; i<(n-1)/2; i++) p=p.next;  
     ListNode t=p.next;  
     p.next=null;  
     ListNode r=null;  
     while (t!=null) {  
       ListNode temp=t.next;  
       t.next=r;  
       r=t;  
       t=temp;  
     }  
     p=head;  
     while (p!=null && r!=null) {  
       if (p.val!=r.val) return false;  
       p=p.next;  
       r=r.next;  
     }  
     return true;  
   }  
 }