Linked List Reversal Example: Is a Linked Word Spelt the Same Backwards?

Find the middle with two speeds, reverse the second half, and compare the halves letter by letter, all without copying the word.

Reversing half of a linked list lets it be read from both ends at once, which answers whether a word stored one letter per node is a palindrome, spelt the same backwards, in O(1) extra memory. Nothing in the question says reverse: the cue is that a list can only be walked forwards, and the check needs the back. Two words are stored this way: stats and stars.

Is each word spelt the same backwards?

stats is, and stars is not: its second letter is t and its second-to-last is r.

The check has three steps. Find the middle with slow and fast pointers, as the Fast and Slow Pointers topic does. Reverse the list from the middle on. Then walk one pointer from the head and one from the reversed half, comparing letters, until the reversed half runs out. The steps show stars.

Checking stars from both ends

Find the middle

text

word: s → t → a → r → s → null
slow: a, where it stopped when fast reached the last letter

Reverse the second half

text

first half: s → t → a → null
reversed half: s → r → a → null

Compare the first letters

text

left: s, right: s
they match: move both on

Compare the second letters

text

left: t, right: r
they differ: not the same backwards

The first half still ends on a, because t's next was never changed, and the reversed half also ends on a, so on an odd word the middle letter is compared with itself. The listing checks both words and then reverses the second half again, so the caller gets its list back as it was.

palindrome.pypy

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None


def build(values):
    head = None
    for val in reversed(values):
        node = ListNode(val)
        node.next = head
        head = node
    return head


def values_of(head):
    values = []
    while head:
        values.append(head.val)
        head = head.next
    return values


def reverse(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev


def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def is_palindrome(head):
    second = reverse(middle(head))
    left, right = head, second
    same = True
    while right:
        if left.val != right.val:
            same = False
            break
        left = left.next
        right = right.next
    reverse(second)
    return same


for word in ["stats", "stars"]:
    head = build(list(word))
    print(f"{word}: {is_palindrome(head)}, after restoring: {''.join(values_of(head))}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

stats: True, after restoring: stats
stars: False, after restoring: stars

Each step is one pass over at most n nodes, so the check is O(n) time and O(1) extra space; copying the letters into an array and comparing from both ends is also O(n) time but O(n) space. Restoring the list matters whenever the caller still uses it, because a check that leaves its input half reversed has changed data it was only asked to read.

Linked Lists

← → move through sections and cards