My AC java Solution, reverse and compare, O(n) time, O(1) space


  • 0
    S
    public class Solution {
        public boolean isPalindrome(ListNode head) {
           ListNode patrol=head;
           int len=0;
           while(patrol!=null){
           		patrol=patrol.next;
           		len++;
           }
           if(len<2) return true;
           //reverse
           patrol=head.next;
           ListNode base =head;
           head.next=null;
           for(int i=0;i<len/2-1;i++){
           		ListNode tmp=patrol.next;
           		patrol.next=base;
           		base=patrol;
           		patrol=tmp;
           }   
           //compare
           if(len%2==1) patrol=patrol.next;
           for(int i=0;i<len/2;i++){
           		if(base.val!=patrol.val) return false;
           		base=base.next;
           		patrol=patrol.next;
           }
           return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.