【第三轮】6.30-7.6 CareerCup 2.7

grassgigi 发表于 2014-6-29 22:55
【解题思路】
Recursion

Recursion占用栈空间，java里面应该还是O(n)空间

【解题思路】
1. if we are allowed to modify the linkedlist, we can reverse the second half in place  and then compare the first half with the second half
2. push elements in the first half to a stack and then compare them with the second half
【时间复杂度】1. O(N)   2. O(N)
【空间复杂度】1. O(1)   2. O (N)
【gist link】 https://gist.github.com/jyhjuzi/32617c7992f3807bd098

【解题思路】
first pass to push every elements in the stack, second pass to compare the pop element from the stack with the list.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/cdb703fcb9b665551ae6

【解题思路】store elements into a stack and pop element from stack and compare to the list
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/startupjing/1f3b016aa1cc20187ec8

【解题思路】
reverse the list and compare with the original one
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/9bc2f720dac8e06c69a1

【解题思路】
use a stack to reverse the first half of the list and then compare
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/23e37c323192dd6f3405

【解题思路】Use slow and fast pointers to find the middle of the linked list. Use a stack to keep track of all integers to see if it is a palindrome.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/ca90d321da5a21c80ed1

【解题思路】use two iterators to find the middle node and put the first half of the list into a new stack
then compare the second half of list with the stack
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/weazord/2936434fce6597344593

============================================================================
Question        : 2.7  Implement a function to check if a linked list is a palindrome.
Solution        : Save all elements in to a python list, and use slicing to check if
                    it is a palindrome
Time Complexity : O(N)
Space Complexity: O(N)
Gist Link       : https://gist.github.com/habina/20fd04778919563f0126
============================================================================

【解题思路】slow-fast pointers find mid node, break it, reverse half and count it, startover form heads of both list, compare value
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】稍后编辑