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

• 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;
next = n->next;
return true;
}
return false;
}
return false;
return false;
next = next->next;
return true;
}
int len = 0;
len++;
}
return len;
}
ListNode *p;
if(len == 1) return true;
}``````

• 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:
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) {
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;
}
}
};``````

• cool. thanks for sharing.

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