【第三轮】6.30-7.6 CareerCup 2.7

2.7  Implement a function to check if a linked list is a palindrome.


回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】reverse the second half, compare it with the first half, then restore the list.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/a8fb05f7c9db8b38b403

【解题思路】c++ 写了两个：第一种用了数组，逆序存入，在重新iterate对比，完全一致则true,遇到不一致返回false
                                        第二种是看了书启发的，快慢runne+stack, push 一半， 之后慢指针和pop出来的对比，遇到不一致返回false, 否则true
                                        (需要注意的是，list 长度可为odd/even, 写判断条件要考虑周全)
【时间复杂度】O(n) 方法一要iterate两遍，方法二一遍
【空间复杂度】O(n) 数组要得相对多一点，stack少一半
https://gist.github.com/xun-gong/6fae52f025d0a6aab959

【解题思路】
Recursion

【时间复杂度】
O(N) call depth

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/1a1a5cc9fafe13b0d87e

补充内容 (2014-7-1 12:46):
【空间复杂度】
O(N) - recursion depth

【gist link】【解题思路】
Recursion

【时间复杂度】
O(N)

【空间复杂度】
O(1)

【gist link】https://gist.github.com/hilda8519/55ba79b63e25ea971166

【解题思路】
其实如果让用extra data structure就好多方法不过都比较trivial,不然就用recursion,@serolins 或者像书上那样。另外如果input是null是返回true还是false应该是问interviewer。书上的意思好像是true

【时间复杂度】
O(N)

【空间复杂度】
O(N) because of recursion

【gist link】
https://gist.github.com/XiaoxiaoLi/97a862556e61369b59d1

【解题思路】Assume data tye is char
1. reverse the list and compare each element.
2. push first half of the list into a stack, continue traverse the list and pop out if the second half matches the first half. return true if the stack is empty after traversal.
3. recursion...
【时间复杂度】
O(2N)
O(N)
【空间复杂度】
O(N)
O(N/2)
【gist link】
https://gist.github.com/ff5d9972e02df9306886
【test case】
null list returns true

【解题思路】Build a new list reverse the original list, then compare their elements
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】
https://gist.github.com/bitcpf/3ed5522deab119c1f576

【解题思路】把linkedlist用list.toArray转化为list后进行比较
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】
https://github.com/donnice/donnice/blob/master/Q2.7