Java Solution by reversing half of the list. O(n) time. O(1) extra space.


  • 0
    A
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    
    //Uses O(n) time and O(1) space.
    
    class Solution {
        
        private ListNode reverse(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode curr=head, prev=null, next=head;
            while(curr!=null) {
                next = curr.next;
                curr.next = prev;
                
                prev = curr;
                curr = next;
            }
            // prev is the new head now.
            return prev;
        }
        
        public boolean isPalindrome(ListNode head) {
            ListNode slow = head, fast = head;
            if (head==null || head.next==null) return true;
            
            // Find the mid point of linked list.
            while(fast!=null && fast.next!=null) {
                fast = fast.next;
                
                if (fast==null || fast.next==null) {
                    break;
                }
                
                fast = fast.next;
                slow = slow.next; 
            } // slow is the mid point of linked list.
                    
            // Temporarily split list into two halves. Reverse the second half
            ListNode head2 = slow.next;
            slow.next=null;
            head2 = reverse(head2);
                    
            // Parse and compare both halves' elements one by one.
            ListNode ptr1 = head, ptr2 = head2;
            while (ptr1 != null && ptr2 != null) {
                if (ptr1.val != ptr2.val) {
                    return false;
                }
                ptr1 = ptr1.next;
                ptr2 = ptr2.next;
            }
            
            // At this point. list is definitely a palindrome.
            //  Even list: Both halves are empty and same val.
            //  Odd list: Both halves have same values but one half has one element remaining. Since single remaining element is also palindrome, it is true.
            
            // Revert the second half of list, connect both halves and return true.
            head2 = reverse(head2);
            slow.next = head2;
            return true;
        }
    }
    
    

Log in to reply
 

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