【第三轮】6.30-7.6 CareerCup 2.7

【解题思路】快慢指针知道middle node，分为first和second两个half。second进行reverse，然后做比较。相等即回文
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/guchang/f929399108d505918262

【解题思路】
Use a fast pointer(iterator) and a slow pointer(iterator).
Fast pointer increments twice each step, while slow pointer
increments once, and push the value into a stack. When fast
pointer reaches end of the list, slow pointer is just in the
middle. Then move slow pointer step by step and compare with
the values stored in stack.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/57c19338b7177820cb3a

//【解题思路】
//利用递归，从中间向两边走
//【时间复杂度】
//O(n)
//【空间复杂度】
//O(1)
//【gist link】
https://gist.github.com/Tsien/2b657a0bc23f0ca63350

【解题思路】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

【解题思路】
Use stack to store the values of the first half nodes
when traversing the second half nodes, compare the value with the one on the top of the stack to check whether it's palindrome

【时间复杂度】
O(n)


【空间复杂度】
O(n)


【gist link】
https://gist.github.com/happyWinner/c144f36610798c6accc3

Solution1
Idea: using two pointers, one slow and one fast, when fast met the tail, which means the slow meet the middle node, and reverse second half of the list, and contrast with the first half, if equal, which means the list is palindrome

Time Complexity: O(n)
Space Complexity: O(n)


Solution2
Idea: Instead of using extra List to store the second half the input list, we can simple use the stack to store the info.

Time Complexity: O(n)
Space Complexity: O(n)

Code:
http://www.jyuan92.com/post-477