• 32.0%

Given a singly linked list, determine if it is a palindrome.

Could you do it in O(n) time and O(1) space?

https://discuss.leetcode.com/topic/18304/share-my-c-solution-o-n-time-and-o-1-memory

Share my C++ solution, O(n) time and O(1) memory

https://discuss.leetcode.com/topic/27605/my-easy-understand-c-solution

My easy understand C++ solution

https://discuss.leetcode.com/topic/18533/reversing-a-list-is-not-considered-o-1-space

Reversing a list is not considered “O(1) space”

It is a common misunderstanding that the space complexity of a program is just how much the size of additional memory space being used besides input. An important prerequisite is neglected the above definition: the input has to be read-only. By definition, changing the input and change it back is not allowed (or the input size should be counted when doing so). Another way of determining the space complexity of a program is to simply look at how much space it has written to. Reversing a singly linked list requires writing to O(n) memory space, thus the space complexities for all “reverse-the-list”-based approaches are O(n), not O(1).

Solving this problem in O(1) space is theoretically impossible due to two simple facts: (1) a program using O(1) space is computationally equivalent to a finite automata, or a regular expression checker; (2) the pumping lemma states that the set of palindrome strings does not form a regular set.

Please change the incorrect problem statement.

https://discuss.leetcode.com/topic/18293/11-lines-12-with-restore-o-n-time-o-1-space/2

11 lines, 12 with restore, O(n) time, O(1) space

O(n) time, O(1) space. The second solution restores the list after changing it.

Solution 1: Reversed first half == Second half?

Phase 1: Reverse the first half while finding the middle.

Phase 2: Compare the reversed first half with the second half.

Solution 2: Play Nice

Same as the above, but while comparing the two halves, restore the list to its original state by reversing the first half back. Not that the OJ or anyone else cares.