Check if a linked list is a palindrome in Python

A sequence is a palindrome when it reads the same forwards and backwards, like 1, 2, 3, 2, 1. In a linked list, each item (a node) holds a value and a link to the next node, so you cannot jump to the last item or read it backwards directly.

The program

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def build_linked_list(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head


def is_palindrome(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values == values[::-1]


for values in [[1, 2, 3, 2, 1], [1, 2, 2, 1], [1, 2, 3], [7], []]:
    head = build_linked_list(values)
    print(values, is_palindrome(head))

[1, 2, 3, 2, 1] True
[1, 2, 2, 1] True
[1, 2, 3] False
[7] True
[] True

How it works

• Each Node has a value and a next link. The last node's next is None, which marks the end.
• build_linked_list() starts from the last value and puts each new node in front, so the list ends up in the right order. head is the first node.
• is_palindrome() follows the links from head until it reaches None, and copies each value into a normal Python list.
• values[::-1] is that list reversed. If the two are equal, the linked list is a palindrome.
• A single value and an empty list both count as palindromes.

Copying the values uses extra memory for every node. A common interview follow-up asks you to do it without that copy: find the middle node, reverse the second half of the links, and compare the two halves.

For a normal Python list

If your data is already a Python list, you do not need the nodes at all:

def is_palindrome(items):
    return items == items[::-1]


print(is_palindrome([1, 2, 3, 2, 1]))
print(is_palindrome([1, 2, 3, 4, 5]))
print(is_palindrome(list("racecar")))

True
False
True

Related programs: Linked list.