Palindrome check on a Python linked list

Why this matters

A palindrome is a sequence that reads the same forwards and backwards. The word racecar is one. The list of numbers 1 -> 2 -> 2 -> 1 is one too. The task is to answer yes or no for a linked list without changing the list.

This is a common interview question because it tests three skills at once. You must move through a list with two pointers at different speeds. You must reverse part of a list. You must leave the list as you found it. The intersection lesson before this one uses the same kind of pointer walk. The reversal idea here is the same one that appears in the module's later lessons on reversing groups of nodes.

The problem: a list only goes one way

A singly linked list has one arrow per node, and every arrow points forward. From the head you can reach the tail. From the tail you cannot step back to the head. A palindrome check needs the values in both directions at once, so the plain list does not give you that for free.

There are three ways to solve it.

1. Copy the values into a Python list, then compare the first value with the last, the second with the second last, and so on. This is easy to write. It needs extra memory the size of the list.
2. Use recursion, which means a function that calls itself to reach the far end of the list and compares on the way back. This also uses extra memory, because each call waits on the call stack. Python also limits how deep the calls may go. The default limit is 1000 calls, which sys.getrecursionlimit() reports on the machine used for this lesson. A recursive check on a 500-node list worked. On a 1000-node list it stopped with RecursionError: maximum recursion depth exceeded. The exact cutoff depends on the function. A later lesson in this module covers that limit.
3. Work on the list itself. Find the middle, reverse the second half so it runs backwards, compare the two halves side by side, then reverse the second half back. This uses only a few extra references, no matter how long the list is.

This lesson uses the third method. It is the one interviewers usually want to see, because it runs in one pass plus a few extra walks and needs no extra list.

Here is the idea in plain terms. If the list is 1 -> 2 -> 2 -> 1, the first half is 1 -> 2. Reverse the second half, which is 2 -> 1, and you get 1 -> 2. The two halves now read the same from the front, so the list is a palindrome. The middle has to be found first, and the list has to be put back afterwards.

In Python every variable holds a reference to an object. The line p = head does not copy the node. Both p and head now point at the same node. A reference here is just a name that leads to a node.

Step 1: find the middle with two pointers

The first step finds the middle of the list. Use two pointers, called slow and fast. Both start at the head. Each turn, slow moves forward one node and fast moves forward two nodes. When fast reaches the end, slow is at the middle, because fast covered twice the distance.

The loop condition must check two things. fast must not be None, and fast.next must not be None. Python checks the first part first, and and stops at the first false part. So when fast is None, Python never reads fast.next. The second check stops the loop before fast.next.next would read an attribute of None.

Python compares with is None and is not None, not with == None. The word is asks whether two names point at the same object. None is a single object, so is is the exact check.

Here is the trace for a list of five values, 1 -> 2 -> 3 -> 2 -> 1. The lines show the node values after each round. These are traces worked out by hand, not program output.

list 1 -> 2 -> 3 -> 2 -> 1 -> null
  round 1: slow=2 fast=3
  round 2: slow=3 fast=1
  middle (slow) = 3

In round 1, slow moves from 1 to 2, and fast moves from 1 to 3. In round 2, slow moves to 3, and fast moves to the last node, 1. Now fast.next is None, so the loop stops. The middle is the node with value 3.

For a list of four values, the middle is different. Here is 1 -> 2 -> 2 -> 1:

list 1 -> 2 -> 2 -> 1 -> null
  round 1: slow=2 fast=2
  round 2: slow=2 fast=None
  middle (slow) = 2

In round 2, fast moves past the end, so it is None. The loop stops. slow is the second 2. With an even count, slow lands on the first node of the second half. With an odd count, slow lands on the middle node.

The second half in both cases starts at slow. Keep this rule in mind, because the next steps depend on it.

Step 2: reverse the second half

Reversing a list means turning every arrow around. The node that pointed to B now points to the node before it, and so on, until the old tail becomes the new head. The function keeps three names. prev remembers the node already reversed. head is the node being turned now. nxt remembers the node that comes after it, so the walk can continue after the arrow changes.

The name next is also a built-in function in Python, so the code uses nxt for the saved node. The name next would work, but it would hide the built-in inside the function.

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

Here is the reversal of 3 -> 5 -> 7, traced one node at a time. These are hand traces.

reverse 3 -> 5 -> 7 -> null
  step 1: prev=3 head=5
  step 2: prev=5 head=7
  step 3: prev=7 head=None
  result 7 -> 5 -> 3 -> null

Step 1 turns the arrow of 3 so it points to None. Then prev is 3 and head moves on to 5. Step 2 turns the arrow of 5 so it points to 3. Step 3 turns the arrow of 7 so it points to 5. Now head is None, and prev is 7, which is the new front of the list.

The middle of the earlier list is the start of the second half. Calling the reversal on slow turns only the second half around. The first half still points forward, and it keeps its original arrows.

Step 3: compare the two halves

Now two pointers walk side by side. p starts at the head of the list. q starts at the head of the reversed second half, which is the old tail. At each step, compare p.val with q.val. If they differ, the list is not a palindrome. If they match, move both forward.

The loop stops when q becomes None. Stopping on q works because the second half is at least as long as the first half. For an even list, both halves are the same length, and both pointers end together. For an odd list, the middle node is the start of the second half, so the second half is one node longer. The extra node is compared with itself, which always matches, so it does no harm. Stopping when q is None covers both cases.

Here is a short trace for 1 -> 2 -> 3 -> 2 -> 1. After step 2 the second half is reversed:

first half:   1 -> 2 -> 3
reversed:     1 -> 2 -> 3

Compare 1 with 1, match. Compare 2 with 2, match. Compare 3 with 3, match. The reversed half is finished, so the loop stops. The result is True.

Step 4: put the second half back

The check is done, but the list has changed. Its second half runs backwards, and the middle node now points to None. If the caller uses the list again, it sees a broken chain. A function that answers a question about a list should not change it. The fourth step reverses the second half again. Reversing a reversed list gives the original order back, so the arrows return to their starting positions.

The reversal function returns the new head, but the restore call does not need it. The original middle node, which is slow, is still in the list. After the second reversal it is the head of the second half again, and the first half still points to it. So the list is whole.

The first half was never changed. Its last node still has its arrow pointing to slow, because the reversal only changed arrows inside the second half. Reversing the second half a second time changes those arrows back.

Worked example 1: an even list that is a palindrome

Take 1 -> 2 -> 2 -> 1. The steps are:

1. Find the middle. The second half starts at the second 2.
2. Reverse the second half. The second half 2 -> 1 becomes 1 -> 2.
3. Compare. The first half is 1 -> 2. Compare 1 with 1, match. Compare 2 with 2, match. The reversed half is finished.
4. Restore. The second half goes back to 2 -> 1. The whole list is 1 -> 2 -> 2 -> 1 again.

The answer is True. The list is unchanged.

Worked example 2: an odd list that is a palindrome

Take 1 -> 2 -> 3 -> 2 -> 1. The middle node is 3. In step 1, slow stops on that 3, so the second half starts at the 3. The second half is 3 -> 2 -> 1, which reverses to 1 -> 2 -> 3.

Step 3 compares the first half, which is 1 -> 2 -> 3, with the reversed half 1 -> 2 -> 3. The three pairs match. The middle node is compared with itself, which is harmless. The answer is True.

Worked example 3: a list that is not a palindrome

Take 1 -> 2 -> 2 -> 3. The middle node is the second 2, so the second half is 2 -> 3. It reverses to 3 -> 2. Now compare the first half with the reversed half. The first pair is 1 and 3. They differ, so the answer is False right away.

This example shows why step 4 must run even when the answer is already known. The loop stops early with break, and then the restore call still runs. If you return from inside the loop, the list stays reversed. The common mistakes section shows what that looks like.

Full program

This program has the four steps as separate parts. build makes a list from a Python list of numbers. show returns the list as text. reverse reverses a list in place and returns the new head. is_palindrome does the four steps. The main part checks nine lists, including an empty list and a one-node list, and prints whether each list is unchanged after the check.

Save the file as palindrome.py and run it with python3 palindrome.py. The output is:

null
  palindrome: True
  list unchanged: True
7 -> null
  palindrome: True
  list unchanged: True
1 -> 2 -> null
  palindrome: False
  list unchanged: True
1 -> 1 -> null
  palindrome: True
  list unchanged: True
1 -> 2 -> 1 -> null
  palindrome: True
  list unchanged: True
1 -> 2 -> 2 -> 1 -> null
  palindrome: True
  list unchanged: True
1 -> 2 -> 3 -> 2 -> 1 -> null
  palindrome: True
  list unchanged: True
1 -> 2 -> 3 -> 4 -> null
  palindrome: False
  list unchanged: True
1 -> 2 -> 2 -> 3 -> null
  palindrome: False
  list unchanged: True

The empty list and the one-node list are palindromes. The two-node list 1 -> 2 is not. Every case says the list is unchanged after the check, which is the goal of step 4.

Each step walks the list at most once, so the total work grows in step with the list length. The extra memory is a few names, which does not grow with the list.

Common mistakes

The first mistake is returning early, before the restore step. The natural way to write the loop is to return False as soon as a pair differs. That return skips step 4. Here is a version that does this:

def returns_early(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second_head = reverse(slow)
    p = head
    q = second_head
    while q is not None:
        if p.val != q.val:
            return False
        p = p.next
        q = q.next
    reverse(second_head)
    return True

Run it on 1 -> 2 -> 3 -> 4. The answer is False, which is correct. But the list is now damaged:

before: 1 -> 2 -> 3 -> 4 -> null
returns: False
after the early return: 1 -> 2 -> 3 -> null

The node 4 is gone from the list. It still exists in memory, but no name reaches it from the head, so it is lost. The second half was reversed, and the early return skipped the restore. The fix is the break used in the program above. A break leaves the loop, and the restore line still runs.

The second mistake is missing the None check in the fast pointer loop. If the loop condition only checks fast, a list with an odd number of nodes fails on the last round, because fast.next is None:

def middle_no_check(head):
    slow = head
    fast = head
    while fast is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

On the list 1 -> 2 -> 3, Python stops with this message. Python also prints a traceback above it, which lists the lines the program was on. The line numbers in your copy will differ from the lesson.

AttributeError: 'NoneType' object has no attribute 'next'

The message says that fast.next is None, and the code then reads .next from it. The check fast.next is not None in the real loop prevents this.

The third mistake is comparing node objects instead of values. In Python, is asks whether two names point at the same object. The == operator also falls back to the same check for a plain class like ListNode, unless the class defines its own rule for equality. Two different nodes that hold the same number are still different objects, so this check reports a mismatch for every pair of separate nodes:

def compare_nodes(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second_head = reverse(slow)
    p = head
    q = second_head
    same = True
    while q is not None:
        if p is not q:
            same = False
            break
        p = p.next
        q = q.next
    reverse(second_head)
    return same

The output shows the problem. The list 1 -> 1 is a palindrome, but the function says no:

compare_nodes on 1 1: False
compare_nodes on 1 2 1: False

The second line is also wrong, because 1 -> 2 -> 1 is a palindrome.

Compare the values with p.val != q.val, as the program above does. Readers who know Java: Python's is plays the role that == plays on references in Java, and Python's == runs the class's __eq__ method, which is identity for a plain class.

Practice

Exercise 1. Trace the middle search on the list 1 -> 2 -> 3 -> 4 -> 5 -> 6. Give the value of slow at the end of each round, and the value of fast. Then say which node is the start of the second half.

Show the answer

Round 1: slow is 2 and fast is 3. Round 2: slow is 3 and fast is 5. Round 3: slow is 4 and fast is None, because fast moved from 5 to the node after 6. The loop stops. The start of the second half is the node 4, which is the fourth of six nodes. The second half is 4 -> 5 -> 6, which reverses to 6 -> 5 -> 4. Comparing 1 with 6 gives a mismatch, so the answer is False. The function returns False for this list.

Exercise 2. Reverse the list 3 -> 5 -> 7 -> None, then reverse the result again. What list do you get?

Show the answer

The first reversal gives 7 -> 5 -> 3 -> None. The second reversal turns it back into 3 -> 5 -> 7 -> None. Reversing twice gives back the original order, which is why step 4 works.

Exercise 3. Run the palindrome check on 1 -> 2 -> 3 -> 2 -> 1 -> 1. Give the answer, and say which comparison makes it fail.

Show the answer

The answer is False. The middle search stops on the second 2, which is the fourth node. The second half is 2 -> 1 -> 1, which reverses to 1 -> 1 -> 2. The first half is 1 -> 2 -> 3. The first comparison is 1 with 1, which matches. The second comparison is 2 with 1, which does not match. The function returns False, and the list is restored to 1 -> 2 -> 3 -> 2 -> 1 -> 1 -> None.

Exercise 4. Trace is_palindrome on the two-node list 5 -> 5. Say where slow stops, what the reversed second half looks like, and what the comparison does.

Show the answer

Round 1 moves slow to the second node and fast to None. The loop stops, so slow is the second 5. The reversed second half is 5, a single node. The comparison has one pair, 5 with 5, which matches. The restore call reverses the one-node list, which changes nothing. The function returns True.

Exercise 5. A student writes the comparison loop as while p is not None: instead of while q is not None:. Run it on the one-node list 7, then on the two-node list 1 -> 1. Explain what happens on the second list.

Show the answer

On 7, the loop runs once. p and q both point to the single node, the values match, and both move to None. The function returns True. On 1 -> 1, the loop does not stop when q runs out. p starts at the head of the whole list, so it walks past the middle and keeps going. After one match, q is None, but p is still on the second node, so the loop body reads q.val and fails:

AttributeError: 'NoneType' object has no attribute 'val'

The same crash happens for any palindrome with two or more nodes, such as 1 -> 1 or 1 -> 2 -> 2 -> 1. The condition while q is not None is correct because the reversed second half is never longer than the walk from the head, so q is always the pointer that runs out first.

Summary

• A singly linked list has arrows in one direction only, so the check must build the reverse direction itself.
• Find the middle with a slow pointer that moves one node and a fast pointer that moves two. The second half starts at the slow pointer.
• Reverse the second half, compare it with the first half, and stop when the reversed half runs out.
• Always reverse the second half back, even when the answer is already False, so the caller gets its list back.
• The method uses a few names and no extra list, so its extra memory does not grow with the list length.