234 palindrome linked list
234. Palindrome Linked List
题目: https://leetcode.com/problems/palindrome-linked-list/
难度: Easy
蠢了一下，
思路是：“先翻转整个链表（in-place），然后和之前的链表比较”，但是这样原链表都变了，肯定错。
如果新建一个链表，然后改造成原来链表的翻转链表，还是可行的，但是空间复杂度就是O(n)了。那还不如直接把List中元素拷贝到数组中直接比较，ac代码如下：
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
vals = []
while head:
vals += head.val,
head = head.next
return vals == vals[::-1]
这道题并不能算Easy吧：
思路二： 要想实现O(1)的空间复杂度，可以找到中间的节点，把linked list拆成两个部分，后半部分linkedlist reverse，然后比较两个linked list值是否相同，看例子：
1 -> 3 -> 1 拆成 1 和 1
1 -> 3 -> 5 ->5 -> 3 -> 1 拆成 1-> 3 -> 5 和 5 -> 3 -> 1
可以使用快慢指针来找到中间的节点。
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast = slow = head
# 找到中间节点
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# 翻转后半部分
prev = None
while slow:
tmp = slow.next
slow.next = prev
prev = slow
slow = tmp
# 比较前后两部分
while prev: # while prev and head:
if prev.val != head.val:
return False
prev = prev.next
head = head.next
return True
给个最终状态的例子：
fast tmp
None prev slow
^ ^ ^
| | |
1 --> 2 --> 3 <-- 2 <-- 1 None
但是注意最后的while prev不能换成while fast, 因为这是总节点数为奇数的情况，如果是偶数情况就不一样了，如下：
tmp
slow
None prev fast
^ ^ ^
| | |
1 --> 2 --> 2 <-- 1 None
