- 32.0%

https://leetcode.com/problems/palindrome-linked-list/#/description

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

Follow up:

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

1 | class Solution { |

我的代码实现

1 | /** |

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

My easy understand C++ solution

1 | class 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.

1 | def isPalindrome(self, head): |

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.

1 | def isPalindrome(self, head): |

Python easy to understand solution with comments (operate nodes directly).

1 | def isPalindrome(self, head): |

https://discuss.leetcode.com/topic/18301/5-lines-python-o-n-time-and-space

5 lines Python, O(n) time and space

I just realized that the O(1) space is only a follow-up, so here’s the obvious one without that.

1 | def isPalindrome(self, head): |