Is Linked List a Palindrome

2 solutions

First solution idea is:

1) Store the node values in a list

2) Check if the list is a palindrome by checking if the reverse of the list is equivalent to the list.

Temporal complexity: O(n), Additional Space complexity: O(n)

# Solution 1
def isPalindrome(head: Optional[ListNode]) -> bool:
    tmp_list = []
    while head:
        tmp_list.append(head.val) # append node val to the list
        head = head.next
        
    # [::-1] reversed the list
    return(tmp_list[::-1]==tmp_list)

Second solution idea is:

1) Stores the first half of the Linked List in reverse order in another Linked List

2) Compare the reversed Linked List of the first half with the Linked List of the second half ([1, 2, 3, 3, 2, 1] -> reversed first half [3, 2, 1], second half: [3, 2, 1])

A fast head (advancing two by two) is used to create find directly the middle of the list to create the reversed first half and to set the head of the second half Linked List at the right place.

Temporal complexity: O(n), Additional Space complexity: O(1) (as the nodes already exist)

# Solution 2
def isPalindrome(head: Optional[ListNode]) -> bool:
    revert_half = None # revert_half that will contains the reversed first half
    fast, slow = head, head # fast will advance two by two and slow head will be set to the middle element
    
    # both fast and fast.next need to exist to advance by two
    while fast and fast.next:
        fast = fast.next.next # advance two by two
        # revert_half.next will take the value of revert_half and revert_half becomes slow
        revert_half, revert_half.next, slow = slow, revert_half, slow.next 

    # adjust the middle
    if fast:
        slow = slow.next

    # check if reversed first half and second half are equivalent
    while slow:
        # if not equivalent for a node returns False
        if slow.val != revert_half.val:
            return(False)
        revert_half, slow = revert_half.next, slow.next
        
    # Otherwise returns True
    return(True)