234-palindrome-linked-list

Try it on leetcode

Description

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?

Solution(Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        return self.optimal(head)
    
    # Time Complexity: O(n)
    # Space Complexity: O(n)
    def naive(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        s = []
        while fast:
            s.append(fast.val)
            fast = fast.next
        return s == s[::-1]
    
    
    # Time Complexity: O(n)
    # Space Complexity: O(n)
    def better(self, head: Optional[ListNode]) -> bool:
        self.front_pointer = head

        def recursively_check(current_node=head):
            if current_node is not None:
                if not recursively_check(current_node.next):
                    return False
                if self.front_pointer.val != current_node.val:
                    return False
                self.front_pointer = self.front_pointer.next
            return True

        return recursively_check()
    
    # Time Complexity: O(n)
    # Space Complexity: O(1)
    def optimal(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return True

        # Find the end of first half and reverse second half.
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)

        # Check whether or not there's a palindrome.
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next

        # Restore the list and return the result.
        first_half_end.next = self.reverse_list(second_half_start)
        return result    

    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous