第234题：回文链表

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def isPalindrome(self, head):
 9         """
10         :type head: ListNode
11         :rtype: bool
12         """
13         if head is None:  # 注意边界
14             return True
15             
16         half_end = self.find_half_end(head)  # 获取前半部分列表的末尾节点
17         head_2 = self.half_reverse(half_end.next)  # 将后半链表进行反转
18         current_1 = head
19         current_2 = head_2
20         result = True
21         while result and current_2 is not None:
22             if current_1.val != current_2.val:
23                 result = False
24             current_1 = current_1.next
25             current_2 = current_2.next
26         half_end.next = self.half_reverse(head_2)  # 将原链表保持原样
27         return result
28 
29     def find_half_end(self, head):  # 快慢指针法获取前半部分链表末尾节点
30         fast = head
31         slow = head
32         while fast.next is not None and fast.next.next is not None:
33             slow = slow.next
34             fast = fast.next.next
35         return slow
36 
37     def half_reverse(self, head):  # 反转链表
38         current = head
39         prev = None 
40         while current is not None:
41             next_node = current.next
42             current.next = prev
43             prev = current
44             current = next_node 
45         return prev