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:

For a given list, we find the mid-point and reverse the list from mid-point to the end of the list, then we can compare these two sub list begin->mid, mid.next->end, if they are the same, which means the original list is a palindrome. 

To find the mid-point, we use the walker- runner technique. 

Time complexity: O(n) and we use constant extra space.

  public boolean isPalindrome(ListNode head) {  
     if(head==null || head.next==null) return true;  
     ListNode walker=head;  
     ListNode runner=head.next;  
     while(runner!=null && runner.next!=null){  
       walker=walker.next;  
       runner=runner.next.next;  
     }  
     ListNode tail=walker.next;  
     while(tail.next!=null){  
       ListNode cur=tail.next;  
       tail.next=cur.next;  
       cur.next=walker.next;  
       walker.next=cur;        
     }  
     while(walker.next!=null){  
       if(head.val!=walker.next.val) return false;  
       head=head.next;  
       walker=walker.next;  
     }  
     return true;  
   }