C++ O(n) time, O(1) space solution


  • 6
    J

    My solution has three parts.

    1. Halve the list into two lists.

    2. Reverse one of the sub lists.

    3. Compare

       bool isPalindrome(ListNode* head) {
       if(!head) return true;
       
       ListNode* slow = head;
       ListNode* fast = slow->next;
       
       // separate
       while(fast && fast->next && fast->next->next) {
           slow = slow->next;
           fast = fast->next->next;
       }
       
       ListNode* head2 = slow->next;
       slow->next = NULL;
       
       ListNode* prev = NULL;
       ListNode* cur = head2;
       ListNode* next = NULL;
       
       //reverse
       while(head2) {
           next = head2->next;
           head2->next = prev;
           prev = head2;
           head2 = next;
       }
       
        ///compare
       head2 = prev;
       while(head && head2) {
           if(head->val != head2->val)
               return false;
               
           head = head->next;
           head2 = head2->next;
       }
       
       return true;
       }

  • 0
    F

    Hi jaewoo. A minor improvement: we can actually reverse the first half while we are moving to the middle using the cursor "slow" so we can compare the two sublists as soon as we separate them up.


  • 0
    J

    That's good point!! Thanks.


  • 0
    B
    This post is deleted!

  • 1
    B

    Can you explain the reverse code, I can not understand.


  • 0
    Z

    We've already modified the list in this case. Should we do that? Of course we can get a 'Accepted' for this particular question, but in real life, we should always remember to 'reverse the list back', right? Otherwise the list will be 'ruined' after calling this function.


  • 0
    H

    Is there a need to consider whether the list length is odd or not when doing the final comparison? I skipped the middle point when there were odd number of nodes in the link list. Not sure how you treat this issue.


  • 0
    J

    @Zhuzeng I agree with your opinion. But, leetcode does not consider changing the input data. I think in real situation, as you stated, we should add some code that revert the input.


  • 0
    J

    @huyc As you may know, if the length of the list is odd, the length of one of the sub lists has exactly one more node compared to another one.

    So, the way to compare two lists is like below:

    step1. compare current nodes
    step2. if current nodes are not identical => return false
    step3. move to next nodes
    step4. if one or both of the current nodes is NULL => return true
    step5. move to step1


  • 0
    H

    @jaewoo Thanks for the explanation. I just realized that I reversed the first half as I searched for the middle point such that there was a need to check the oddness at comparison. If the second half was reversed just as you did, we could just skip the comparison when one of the sublists reached NULL.


Log in to reply
 

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