[leetcode] 234. Palindrome Linked List

 

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

 

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 

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

 

 

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
            
        list_ = [] 
        while head:
            list_.append(head.val)
            head = head.next 
            
        flag = True 

        while len(list_) > 1:
            if list_.pop(0) != list_.pop(-1):
                flag = False
            
        return flag

 

 

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        q = collections.deque()
        
        if not head:
            return True 
            
        
        node = head 
        while node is not None:
            q.append(node.val)
            node = node.next 
             

        while len(q) > 1:
            if q.popleft() != q.pop():
                return False 
            
        return True

 

 

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        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, rev = slow.next , rev.next 
            
        return not rev