The fastest c++ solution,complete in o(n) time and o(1) space


  • 1
    V
    class Solution {
    public:
    bool isPalindrome(ListNode* head) {
        ListNode *node=head,*pt1,*pt2,*pt3;
        if(!node) return true;
        int num=0,iter;
        while(node) {num++;node=node->next;}
        if(num<2) return true;
        pt1=head;
        pt2=pt1->next;
        pt1->next=NULL;
        iter=num%2? (num-1)/2 :num/2-1;
        for(int i=0;i<iter;i++)
        {
            pt3=pt2->next;
            pt2->next=pt1;
            pt1=pt2;
            pt2=pt3;
        }
        if(num%2) pt1=pt1->next;
        while(pt1&&pt2)
          if(pt1->val!=pt2->val)
            return false;
          else
          {
              pt1=pt1->next;
              pt2=pt2->next;
          }
        return true;
    }
    };
    

    0_1472721247627_Screenshot from 2016-09-01 16:48:55.png


  • 0
    H

    it is a smart idea


Log in to reply
 

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