今天刷leetcode的Palindrome Linked List這道題，要求判斷一個(gè)單鏈表是不是一個(gè)回文串轴咱，要求空間O(1) 時(shí)間O(n).
最簡單辦法就是反轉(zhuǎn)后面一半的鏈表汛蝙，在一次比較就行了。但是苦于不知道是否能修改原始輸入值朴肺，遲遲不敢這樣做窖剑。
無奈看了下討論區(qū)：
有大神@wangmenghui就提出了 Reversing a list is not considered "O(1) space" 這樣的觀點(diǎn)非常有意思。
先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.
