234. palindrome linked list

Description

Difficulty: Easy

Given a singly linked list, determine if it is a palindrome.

Follow up:

Could you do it in O(n) time and O(1) space?

题意:

判断一个链表是否回文。

Solution

最简单的想法是把链表的值按顺序输出到一个数组,在判断数组是否回文;
判断数组是否回文,也就是判断前一半的逆序是否与后一半相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class (object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return True
link_list = []
p = head
while p:
link_list.append(p.val)
p = p.next
length = len(link_list)
if length % 2 == 0:
return link_list[:(length / 2)] == link_list[(length / 2):][::-1]
else:
return link_list[:(length / 2)] == link_list[(length / 2) + 1:][::-1]