DSA Palindrome Linked List

The problem

A palindrome reads the same forwards and backwards. The word level is a palindrome. The list 1, 2, 1 is a palindrome too.

The problem gives the head of a linked list. The answer is True when the values read the same in both directions. The answer is False otherwise.

Nothing is added or removed. The check only reads the values in place. An empty list and a single node both count as palindromes.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


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


cases = [
    ([1, 2, 2, 1], True),
    ([1, 2, 3, 2, 1], True),
    ([1, 2, 3], False),
    ([1, 2], False),
    ([9], True),
]
for values, expected in cases:
    print(render(build(values)), "| palindrome:", expected)

Read the two passing rows apart. The first has an even length, with a doubled middle pair. The second has an odd length, with a single centre node holding 3.

Both failing rows fail on an outer pair. In the row 1, 2 the only pair already differs. In the row 1, 2, 3 the ends 1 and 3 differ. A mismatch hidden deeper inside appears in the edge cases at the end of this article.

Intuition

The easy first idea copies the values into a plain Python list. A list can be read from both ends. The chain itself cannot.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


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


head = build([1, 2, 3, 2, 1])
values = values_of(head)
print("copied values:", values)
print("first pair:", values[0], values[-1])
print("second pair:", values[1], values[-2])
print("centre value:", values[len(values) // 2])

The copy makes the check trivial. One index walks in from the left. Another walks in from the right.

The cost is a full second list. Every value is stored twice during the check. The chain's own links go unused, even though they already encode the order.

Brute force

The brute force is that copy, finished. Build the value list. Compare it with its own reverse.

Reversing a plain list is cheap to write. The comparison then walks every pair. A single differing pair settles the answer.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


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


def is_palindrome_brute(head):
    values = values_of(head)
    return values == values[::-1]

cases = [
    [1, 2, 2, 1],
    [1, 2, 3, 2, 1],
    [1, 2, 3],
    [1, 2],
    [9],
]
for values in cases:
    print(values, "palindrome:", is_palindrome_brute(build(values)), "copied values:", len(values))

Every case from the start of the article passes. The last column counts the price. The copy holds as many values as the chain holds nodes.

The time cost is fine. The space cost is the flaw. A check that only reads should not need storage that grows with the list.

The optimal solution: split, reverse, compare

Reverse the second half in place, then walk the two halves side by side. That one sentence is the whole method.

Three known patterns compose it. A fast-slow walk finds the middle. A reversing walk flips the second half. A plain walk then compares pairs.

On an odd-length list the middle node joins the second half. After the flip it compares against itself through the two walkers. A centre value always matches itself, so the odd case needs no special branch.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


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


def reverse(head):
    prev = None
    node = head
    while node is not None:
        nxt = node.next
        node.next = prev
        prev = node
        node = nxt
    return prev


def is_palindrome(head):
    if head is None or head.next is None:
        return True
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = reverse(slow)
    first = head
    while second is not None:
        if first.value != second.value:
            return False
        first = first.next
        second = second.next
    return True


cases = [
    [1, 2, 2, 1],
    [1, 2, 3, 2, 1],
    [1, 2, 3],
    [1, 2],
    [9],
]
for values in cases:
    print(values, "palindrome:", is_palindrome(build(values)))

All five cases pass. The even palindrome passes every pair. The odd palindrome passes too, centre included.

No value list is built. The only new storage is a handful of pointers. The trade is that the second half is left reversed, which the last section returns to.

Walkthrough

Watch the check on [1, 2, 3, 2, 1]. The printout shows the middle, the flipped second half, and each compared pair.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


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


def reverse(head):
    prev = None
    node = head
    while node is not None:
        nxt = node.next
        node.next = prev
        prev = node
        node = nxt
    return prev

head = build([1, 2, 3, 2, 1])
print("list:", render(head))
slow = head
fast = head
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
print("middle value:", slow.value)
print("second half:", render(slow))
second = reverse(slow)
print("second half reversed:", render(second))
first = head
while second is not None:
    print("compare", first.value, "with", second.value, "match:", first.value == second.value)
    first = first.next
    second = second.next

The fast-slow walk stops with slow on 3, the centre. The second half starts there. It reads 3, 2, 1 before the flip.

The flip turns that half into 1, 2, 3. The pairs then line up with the first half in order. The last pair compares the centre node with itself, and it matches.

Complexity

The time cost is O(n) for a list of n nodes. Three walks cross the chain or its halves, and each walk is a straight line of steps.

The space cost is O(1). The check stores a few pointers and no copy, so its storage does not grow with the list.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


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


def brute_copies(head):
    return len(values_of(head))

def solution_comparisons(values):
    head = build(values)
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = reverse(slow)
    comparisons = 0
    first = head
    while second is not None:
        comparisons += 1
        first = first.next
        second = second.next
    return comparisons

def reverse(head):
    prev = None
    node = head
    while node is not None:
        nxt = node.next
        node.next = prev
        prev = node
        node = nxt
    return prev

for size in [4, 8, 16]:
    values = list(range(1, size // 2 + 1)) + list(range(size // 2, 0, -1))
    print("nodes", size, "brute copies:", brute_copies(build(values)), "solution comparisons:", solution_comparisons(values))

The brute copy grows with the full list. The solution comparisons grow with only half of it. Doubling the nodes doubles both counts.

The growth rates match. The difference is space. One method stores every value again, and the other stores none.

Edge cases and pitfalls

The empty list passes. The single node passes. Both guards return before any split happens, so no pointer reads a missing next link.

Two nodes form the smallest real test. Equal values pass. Different values fail on the first and only pair.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


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


def reverse(head):
    prev = None
    node = head
    while node is not None:
        nxt = node.next
        node.next = prev
        prev = node
        node = nxt
    return prev


def is_palindrome(head):
    if head is None or head.next is None:
        return True
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = reverse(slow)
    first = head
    while second is not None:
        if first.value != second.value:
            return False
        first = first.next
        second = second.next
    return True


print("empty:", is_palindrome(build([])))
print("single:", is_palindrome(build([9])))
print("two equal:", is_palindrome(build([4, 4])))
print("two different:", is_palindrome(build([4, 5])))
print("late mismatch:", is_palindrome(build([1, 2, 3, 1])))

The late mismatch row deserves a look. Its outer pair matches, 1 with 1. The inner pair fails, 2 against 3, and the check stops there.

The lasting pitfall is the rewiring. The check leaves the second half reversed, because nothing flips it back. A caller that still needs the original list must restore that half after the check.