O(1) space O(n) time 24ms c++ solution


  • 0
    Y
    class Solution {
    public:
        bool compare(ListNode* head1, ListNode* head2)
        {
            for(;head1!=NULL&&head2!=NULL;head1=head1->next, head2=head2->next)
            {
                if(head1->val!=head2->val)
                {
                    return false;
                }
            }
            return true;
        }
    
        int measure(ListNode* head)
        {
            int count=0;
            while(head!=NULL)
            {
                count++;
                head=head->next;
            }
            return count;
        }
        bool isPalindrome(ListNode* head) {
            int n = measure(head);
            /*
            if(n==1)
            {
                return true;
            }
            */
            int middle = n/2;
            cout<<middle<<'\n';
            ListNode* prev=NULL;
            ListNode* cur=head;
            ListNode* next=head;
            for(int i=0;i<middle;i++)
            {
                next=cur->next;
                cur->next=prev;
                prev=cur;
                cur=next;
            }
            head=prev;
            cout<<"head: "<<head<<'\n';
            ListNode*head2;
            head2=cur;
            if(n%2==1)
            {
                head2=head2->next;
                cout<<"head2: "<<head2<<'\n';
                cout<<cur->val<<'\n';
                //delete cur;
            }
            return compare(head, head2);
        }
    };

Log in to reply
 

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