Daily Leetcode 234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

问题描述：

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

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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

题目分析：

这题难度不大，给定一个单链表，我们需要判断它是不是回文串。

将链表的前半部分存在栈中，利用栈先入后出的特性，将链表后半部分元素值与栈中元素值一一对比，全部相同则说明是回文串，反之，则不是。

代码：

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        if not head or not head.next:
            return True
        
        length = 0
        tmp, half = head, head
        stack = []
        
        while tmp:
            length+=1
            tmp = tmp.next
            
        halfLength = length / 2
        
        for i in range(halfLength):
            stack.append(half.val)
            half = half.next
        
        if length % 2 != 0:
            half = half.next
            
        while half:
            current = stack[halfLength - 1]
            if half.val != current:
                return False
            half = half.next
            halfLength-=1
        
        return True

Follow up

这一题的Follow up是要求我们能够在O(n)时间复杂度、以及O(1)空间复杂度的条件下解决这个问题，我的代码并没有达到题目要求，在讨论区，我看到了更好的解法：

思路1

采用快慢指针

思路2

翻转前半部分或后半部分链表，与其余部分进行比较

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