234 palindrome linked list

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def (self, head):
self.list = []
pt = head
while pt:
self.list.append(pt)
pt = pt.next
midR = len(self.list) / 2 if len(self.list) % 2 == 0 else (len(self.list)+1) /2
midL = len(self.list) / 2 - 1 if len(self.list) % 2 == 0 else midR-2
while midR <= len(self.list) and midL >= 0:
if self.list[midR].val != self.list[midL].val:
return False
midR+=1
midL-=1
return True

Time complexity: O(1.5n)
Space complexity: O(2)

store list in a array(python list)
compare node start from middle, if val not equal, return false

Best Solution

1
2
3
4
5
6
7
8
9
10
def (self, head):
"""
:type head: ListNode
:rtype: bool
"""
s = []
while head is not None:
s.append(head.val)
head = head.next
return s == list(reversed(s))

Time complexity: O(n)
Space complexity: O(3)

use python defined function to check if reversed list equal to original list