clean O(n) solution(O(1) space) run time 19ms beats 72%


  • 0
    A

    Approach is to reverse one half of the list while traversing using slow and fast pointers and then comparing the two halves with one another.We can easily tell whether the list has odd number of nodes or even using the position of fast pointer at the end of traversal(fast pointer is at null in case of odd number of nodes and at last node in case of even number of nodes as we have initialised fast pointer from 2nd node).
    Here is my cpp solution:-

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(head==NULL || head->next==NULL)return true;
            ListNode* slow=head,*fast=head->next;
            ListNode* prev=NULL,*next=NULL,*head1,*head2;
            while(fast!=NULL && fast->next!=NULL)
            {
                next=slow->next;
                slow->next=prev;
                prev=slow;
                slow=next;
                fast=fast->next->next;
            }
            if(fast==NULL)
            {
                //odd nodes
                head1=prev;
                head2=slow->next;
            }
            else
            {
                //even nodes
                head2=slow->next;
                slow->next=prev;
                head1=slow;
                
            }
            while(head1!=NULL && head2!=NULL)
            {
                if(head1->val!=head2->val)
                {
                    return false;
                }
                head1=head1->next;
                head2=head2->next;
            }
            if(head1==NULL && head2==NULL)return true;
            return false;
        }
    };
    

Log in to reply
 

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