LeetCode 234. Palindrome Linked List

题目

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

分析

判断单链表是否是回文

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
pass
'''
O(n) time, O(1) space. The second solution restores the list after changing it.
Solution 1: Reversed first half == Second half?
Phase 1: Reverse the first half while finding the middle.
Phase 2: Compare the reversed first half with the second half.
'''
def isPalindrome(self, head):
rev = None
slow = fast = head
while fast and fast.next:
fast = fast.next.next
rev, rev.next, slow = slow, rev, slow.next # 巧妙的实现了翻转
if fast:
slow = slow.next
while rev and rev.val == slow.val:
slow = slow.next
rev = rev.next
return not rev # 如果是回文,rev 最后应该为 None
'''
Solution 2: Play Nice
Same as the above, but while comparing the two halves, restore the list to its original state by reversing the first half back. Not that the OJ or anyone else cares.
'''
def isPalindrome(self, head):
rev = None
fast = head
while fast and fast.next:
fast = fast.next.next
rev, rev.next, head = head, rev, head.next
tail = head.next if fast else head
isPali = True
while rev:
isPali = isPali and rev.val == tail.val
head, head.next, rev = rev, head, rev.next # 判断回文的过程又翻转一次
tail = tail.next
return isPali

点评

关键是找到链表的中间节点,可以用快慢双指针实现。在找中间节点的过程,可以将前半部分链表翻转