Leetcode 234. Palindrome Linked List
方法1
思路：将链表中的元素都保存list中，并判断这个list和反转后的list，是否相同，如果相同，则回文；否则，则不回文。
性能分析：时间复杂度为O(n);空间复杂度为O(n) [因为用到了extra space list]
方法2
思路：将链表等分为两部分，判断前半部分和后半部分的逆序是否相等，如果相等，则回文，否则不回文。
性能分析：时间复杂度为O(n)；空间复杂度为O(1)[no extra space
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def list_len(self, head):
p = head
count = 1
while(p):
p = p.next
count += 1
return count - 1
def get_i_node(self, head, i):
p = head
count = 1
while(count <= i-1):
p = p.next
count += 1
return p
def reverselist(self, head):
pre = None
cur = head
lat = cur.next
while(lat):
cur.next = pre
pre = cur
cur = lat
lat = lat.next
cur.next = pre
return cur
def equals_list(self, head1, head2):
p = head1
q = head2
while(p and q):
if p.val != q.val:
return False
else:
p = p.next
q = q.next
return True
def isPalindrome1(self, head): # 方法一：时间复杂度为O(n),空间复杂度为O(1)
if not head:
return True
tmp_len = self.list_len(head)
if tmp_len == 1:
return True
if tmp_len % 2:
i = (tmp_len + 1) // 2 + 1
else:
i = tmp_len // 2 + 1
second_head = self.get_i_node(head, i)
second_head = self.reverselist(second_head)
return self.equals_list(head, second_head)
def isPalindrome2(self, head): # 方法二：时间复杂度为O(n),空间复杂度为O(n)
"""
:type head: ListNode
:rtype: bool
"""
elem_list = []
p = head
while(p):
elem_list.append(p.val)
p = p.next
return elem_list == elem_list[::-1]
left = 0
right = len(elem_list) - 1
while(left <= right):
if elem_list[left] == elem_list[right]:
left += 1
right -= 1
else:
return False
if right < left:
return True
]
作者：想要成为大牛的李同学
