Share my O(n) time and O(1) space solution with three pointers -- C++ version


  • 0
    L
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(head==NULL||head->next==NULL) return true;
            int count=1;
            ListNode* tmp=head;
            for(;tmp->next!=NULL;count++){
                tmp=tmp->next;
            }
            ListNode* pre=NULL,*cur=head,*nex=head->next;
            for(int i=0;i<(count+1)/2;i++){
                cur->next=pre;
                pre=cur;
                cur=nex;
                nex=nex->next;
            }
            if(count%2==1) pre=pre->next;
            while(pre||cur){
                if(pre->val!=cur->val) return false;
                pre=pre->next;
                cur=cur->next;
            }
            return true;
        }
    };

  • 0
    L

    A new version, with 24 ms. Simpler, and faster.

    if(head==NULL||head->next==NULL) return true;
        ListNode* fast=head;
        ListNode* pre=NULL,*cur=head,*nex=head->next;
        while(fast&&fast->next){
            fast=fast->next->next;
            cur->next=pre;
            pre=cur;
            cur=nex;
            nex=nex->next;
        }
        if(fast) cur=cur->next;
        while(pre&&cur){
            if(pre->val!=cur->val) return false;
            pre=pre->next;
            cur=cur->next;
        }
        return true;

Log in to reply
 

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