234. Palindrome Linked List

Easy


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

 

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:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def get_head_mid(self, head):
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow


    def reverse_mid(self, head):
        prev = None
        current = head
        while current:
            temp = current.next 
            current.next = prev
            prev = current
            current = temp

        return prev


    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        head_first = head
        head_mid = self.get_head_mid(head)
        new_rev_head = self.reverse_mid(head_mid)

        head_last = new_rev_head

        while head_last:
            if head_first.val != head_last.val:
                return False
            head_first = head_first.next
            head_last = head_last.next 

        return True

Random Note


From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict