Is my solution O(n) time and O(1) space?


  • 0
    L

    it took me sometime to figure out below recursion solution, accepted by OJ at 28ms,
    I think it is O(n) time, but is it O(1) space?

    bool helper(ListNode* head, int cur, int len, ListNode*& next){
      if(cur == (len/2)-1){
        ListNode* n;
        if(len&1) n = head->next->next;
        else n = head->next;
        if(head->val == n->val){
          next = n->next;
          return true;
        }
        return false;
      }
      if(!helper(head->next, cur+1, len, next))
        return false;
      if(head->val != next->val)
        return false;
      next = next->next;
      return true;
    }
    int listLen(ListNode* head){
      int len = 0;
      while(head){
        head = head->next;
        len++;
      }
      return len;
    }
    bool isPalindrome(ListNode* head) {
      ListNode *p;
      if(!head) return true;
      int len = listLen(head);
      if(len == 1) return true;
      return helper(head, 0, len, p);
    }

  • 0
    E

    I came up a similar solution as yours. Mine runs 28ms.

    I think this depends on how you define space usage. The recursion itself uses space that is O(n). But you don't use additional O(n) memory except for recursion.

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if (!head) return true;
            ListNode * probe = head;
            int len = 1;
            ListNode sentinel(0);
            while (probe->next) {
                len++;
                probe = probe->next;
            }
            if (!probe->next) probe->next = &sentinel;
            ListNode * return_ptr = palindrome_traversal(head, len);
            if (return_ptr) {
                probe->next = NULL;
                return true;
            } else {
                probe->next = NULL;
                return false;
            }
        }
    private:
        ListNode * palindrome_traversal(ListNode * head, int len) {
            if (len == 2) {
                if (head->val == head->next->val) return head->next->next;
                else return NULL;
            }
            if (len == 1) return head->next;
            ListNode * return_ptr = palindrome_traversal(head->next, len - 2);
            if (return_ptr) {
                if (head->val == return_ptr->val) return return_ptr->next;
                else return NULL;
            } else {
                return NULL;
            }
        }
    };

  • 0
    L

    cool. thanks for sharing.


Log in to reply
 

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