C++ time: O(n) space:O(1) easy to understand with comments.


  • 2
    H

    first reverse the second half ans compare it with first half to check whether linked list is palindrome or not.

         struct ListNode * rev(struct ListNode * head)  //function for reverse the list
         {
             struct ListNode *a=0,*b=head,*c,*hh;
             if(b) c=b->next;
             while(b)
             {
             b->next=a;
             a=b;
             b=c;
             if(c) c=c->next;
             }
             return a;
         }
         
        class Solution {
        public:
            bool isPalindrome(ListNode* head) {
                struct ListNode *s,*f;
                s=f=head;
                if(!head || !head->next) return true;
                while(f->next && f->next->next)
                {
                    s=s->next;
                    f=f->next->next;
                }
                 s=s->next;
                 s=rev(s);   // s is reversed second half
                 f=head;
                 while(s!=0)  //compare first half with second half
                 {
                     if(s->val==f->val){s=s->next,f=f->next;}
                     else return false;
                 }
                 return true;
                 
            }
        };

  • -1
    M
     bool isPalindrome(ListNode* head) {
            stack<int> s;
            int length=0;
            ListNode* move=head;
            while(move!=NULL)
            {
                s.push(move->val);
                length++;
                move=move->next;
            };
            if(length==0||length==1)
            return true;
            move=head;
            for(int i=0;i<length/2;i++)
            {
                if(s.top()!=move->val)
                return false;
                move=move->next;
                s.pop();
            };
            return true;
            
        }

  • -1
    W
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            ListNode *curr = head;
            long forward = 0, backward = 0;
            int i = 0;
            while(curr){
                forward = (forward << 1) + curr->val;
                backward += (long)(1 << i++) * (long)curr->val;
                curr = curr->next;
            }
            return forward == backward;
            
        }
    };

  • 0
    G

    This might not pass on a list that has many INT_MAX elements.


Log in to reply
 

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