Clear and simple Java solution with examples based on reverse linkedlist beats 87.12% submissions


  • 2
    J
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null) return true;
            ListNode pre = null;
            ListNode cur = head;
            ListNode next = null;
            ListNode fast = head;
            //reverse first half list and get the mid
            //a->b->c->b->a->null res: null<-a<-b c->b->a->null pre = b cur = c fast = a
            //a->b->b->a->null res: null<-a b->b->a->null pre = a cur = b fast = b2
            while(fast.next != null && fast.next.next != null){
                fast = fast.next.next;
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            
            if(fast.next == null){
                //if odd, move cur one step
                cur = cur.next;
            }else{
                //if even, move cur two steps and compare
                if(cur.val != cur.next.val) return false;
                else cur = cur.next.next;
            }
            
            while(cur != null){
                if(cur.val != pre.val) return false;
                cur = cur.next;
                pre = pre.next;
            }
            return true;
        }
    }

Log in to reply
 

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