O(n) time and O(1) space c++, fast and slow pointer


  • 0
    C
    class Solution {
    public:
        bool isPalindrome(ListNode* slow, ListNode* fast)
        {
          if (fast == nullptr) {
            half = slow;
            return true;
          }
          if (fast->next == nullptr) {
            half = slow->next;
            return true;
          }
    
          if (isPalindrome(slow->next, fast->next->next) && slow->val == half->val) {
            half = half->next;
            return true;
          }
    
          return false;
        }
    
        bool isPalindrome(ListNode* head) {
          return isPalindrome(head, head);
        }
    
        ListNode* half;
    };

  • 0
    A

    recursion method may not mean O(1) space


  • 0

    The recursive solution is beautiful, but actually it will use the stack space. So it is O(n).


Log in to reply
 

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