A simple code with reversing from the middle


  • 0
    L

    The basic idea is to reverse from the middle and you could safely ignore the odd or even size as the odd number at the middle will not be compared at all. Here is the code:

       public boolean isPalindrome(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            ListNode prev = null;
            while(fast!=null && fast.next!=null) {
                fast = fast.next.next;
                prev = slow;
                slow = slow.next;
            }
            
            ListNode first =head;
            if(prev!=null)
                prev.next = null;
            ListNode reversed = reverse(slow);
            while(first!=null && reversed!=null) {
                if(first.val!=reversed.val) {
                    return false;
                }
                first = first.next;
                reversed = reversed.next;
            }
            
            return true;
        }
        
        private ListNode reverse(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            ListNode next = curr;
            while(curr!=null) {
                next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    

Log in to reply
 

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