Palindrome List

题目描述

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

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

解题方法

简单方法

建一个新的reverse list, 然后比较，但是需要O(n)的空间复杂度

follow up解法

• 求得长度
• reverse前半部分
• 然后再从两个头比较

注意点

• 长度的奇偶性

Solution

# 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 not head:
            return True
        length = self.getLength(head)
        half = length / 2
        p = 0
        pre = None
        cur = head
        # reverse first half
        while p < half:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
            p += 1
        if length % 2 != 0:
            cur = cur.next
        while pre and cur:
            if pre.val != cur.val:
                return False
            pre = pre.next
            cur = cur.next

        return True


    def getLength(self, head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

Reference