Palindrome Linked List

今天刷leetcode的Palindrome Linked List这道题，要求判断一个单链表是不是一个回文串，要求空间O(1) 时间O(n).

最简单办法就是反转后面一半的链表，在一次比较就行了。但是苦于不知道是否能修改原始输入值，迟迟不敢这样做。
无奈看了下讨论区：
有大神@wangmenghui就提出了 Reversing a list is not considered "O(1) space" 这样的观点非常有意思。

先mark一记。

@wangmenghui said in 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.