uuugh -_-

linked_list_is_a_palindrome.py

import sys
import collections

Node = collections.namedtuple('Node', ['value', 'next'])


def check_palindrome_n2(head_node):
    seen = []
    if not head_node.next:
        return True
    current_node = head_node
    while current_node:
        even_match = seen and current_node.value == seen[-1]
        odd_match = seen and current_node.value.next == seen[-1]
        if (even_match or odd_match) and check_symmetricity(seen, current_node.next if odd_match else current_node):
            return True
        current_node = current_node.next
        seen.append(current_node.value)
    return False


def check_symmetricity(seen, node_from):
    n = len(seen) - 1
    node = node_from
    for i, left_part_value in enumerate(reversed(seen)): 
        if not eq(left_part_value, node_from.value):
            return False
        if not node_from.next and i != n:
            return False
        node = node.next
    return True

def check_palindrome_naive(head_node):
    seen = []
    if not head_node.next:
        return True
    current_node = head_node
    while current_node:
        seen.append(current_node.value)
        current_node = current_node.next
    n = len(seen)
    for i in range(int(n/2)):
        if seen[i] != seen[n-i]:
            return False
    return True


def check_palindrome_fp(head_node):
    pointer = head_node
    fast_pointer = head_node
    while fast_pointer and fast_pointer.next:
        pointer = pointer.next
        fast_pointer = fast_pointer.next.next
    reverse_half_pointer = pointer.next
    while reverse_half_pointer.next:
        tmp = reverse_half_pointer.next
        reverse_half_pointer.next = pointer
        pointer = tmp
    pointer = head_node
    while reverse_half_pointer and pointer:
        if reverse_half_pointer.value != pointer.value:
            return False
        reverse_half_pointer = reverse_half_pointer.next
        pointer = pointer.next
    return True


def eq(v1, v2):
    return v1 == v2


if __name__ == 'main':
    if len(sys.argv) != 1:
        print('Expecting a single string as input')
        sys.exit(1)
    input_string = sys.argv[0]
    if not input_string:
        sys.exit(1)
    l = Node(input_string[-1], None)
    for s in reversed(input_string[:-1]):
        l = Node(s, l)
    print(check_palindrome(l))