原题

设计一种方式检查一个链表是否为回文链表。

样例
1->2->1就是一个回文链表。

解题思路

• 方法一：快慢指针，慢指针一边走一边将经过的节点放入stack，当快指针走到终点，慢指针正好走到中点，并且已经将前半段放入stack，根据stack的特性，之后依次取出跟后半段比对。
• 方法二：依旧使用快慢指针，取到中点，然后将后半段翻转，比较

完整代码

# 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
        """
        if head == None or head.next == None:
            return True
        
        stack = []
        slow, fast = head, head
        while fast != None and fast.next != None:
            stack.append(slow.val)
            slow = slow.next
            fast = fast.next.next
        
        if fast == None:
            pass
        else:
            slow = slow.next
        
        while slow != None:
            cur = stack.pop()
            if slow.val != cur:
                return False
            slow = slow.next
            
        return True
        
# 方法二
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None or head.next == None:
            return True
        
        slow, fast = head, head
        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
        
        if fast == None:
            secHalf = self.reverse(slow)
        else:
            secHalf = self.reverse(slow.next)
        
        while secHalf != None:
            if secHalf.val != head.val:
                return False
            secHalf = secHalf.next
            head = head.next
            
        return True
    
    def reverse(self, head):
        if not head:
            return head
        
        prev = None
        while head != None:
            temp = head.next
            head.next = prev
            prev = head
            head = temp
        
        return prev