Check Palindrome in O(n) time and O(1) extra space


  • 0
    H

    Solution is dependent on the reverse of the linked list. The solution is as follows:
    first find the middle of the linked list and now reverse the half of the linked list.
    now check whether the linked lists are equal or not. If not return false. if any of the list is empty
    and all the element of both list are same then reverse the list from the middle and return true.
    The code is as follows:

    bool isPalindrome(struct ListNode* head) {
        
        struct ListNode *slow,*fast;
        slow=head;
        fast=head;
        
        for(;fast!=NULL;)
        {
            slow=slow->next;
            fast=fast->next;
            if(fast==NULL)
                break;
            
            fast=fast->next;
        }
    
        slow=reverse(slow);
        
        struct ListNode *ptr1,*ptr2;
        
        for(ptr1=head,ptr2=slow;ptr1!=NULL && ptr2!=NULL;)
        {
            if(ptr1->val!=ptr2->val)
                return false;
            ptr1=ptr1->next;
            ptr2=ptr2->next;
        }
        
        slow=reverse(slow);
        return true;
    }
    
    

Log in to reply
 

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