【Leetcode】234—Palindrome Linked

一、题目描述

请判断一个链表是否为回文链表。
示例：

输入: 1->2
输出: false

输入: 1->2->2->1
输出: true

进阶：你能否用O(n)时间复杂度和O(1)空间复杂度解决此题？

二、代码实现

算法有以下几种：
1、遍历整个链表，将链表每个节点的值记录在数组，再判断数组是不是一个回文数组，时间复杂度O(n)，但空间复杂度也为O(n)，不满足空间复杂度要求。
2、利用栈先进后厨的性质，将链表前半段压入栈中，再逐个弹出与链表后半段比较。时间复杂度O(n)，但仍需要n/2的栈空间，空间复杂度为O(n)。
3、反转链表法：将链表后半段原地翻转，再将前半段、后半段依次比较，判断是否相等。时间复杂度O(n)、空间复杂度O(1)。

方法一、回文数组

# 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
        """
        NodeList = []
        while head:
            NodeList.append(head.val)
            head = head.next
        return NodeList == NodeList[::-1]

方法二、反转链表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, cur):
        pre = None
        while cur:
            last = cur.next
            cur.next = pre
            pre = cur
            cur = last
        return pre
            
        
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head ==  None or head.next == None: return True
        slow = head
        fast = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        newhead = self.reverseList(slow.next)
        while newhead:
            if  newhead.val != head.val:
                return False
            newhead = newhead.next
            head = head.next
        return True