Palindrome linked list

Why this matters

A palindrome is a sequence that reads the same forwards and backwards. The word "level" is one. So is the list of numbers 1, 2, 1. The question here is whether a singly linked list is a palindrome, using only the nodes and pointers already in the list.

The obvious approach copies the values into an array, then checks the array from both ends. That works, but it uses extra memory for the copy. The method in this lesson uses only a few pointer variables, and it does not change what the list contains when it finishes. This is a good exercise because it combines three skills: walking a list with two pointers at different speeds, reversing part of a list, and putting the list back the way it was.

This lesson assumes you know what a node and a pointer are, and how to walk a singly linked list. Lesson 1 of this module covers those basics. The lesson on finding the shared tail of two lists uses a similar two-pointer walk.

The problem in plain words

A singly linked list is a chain of nodes. Each node holds a value and a pointer to the next node, which is the address of that node in memory. The last node points to nullptr, which is C++ for "no node here".

You are given the head of a list, which is the address of the first node. Return true if the values read the same from the front and from the back, and false otherwise. The method must use a fixed amount of extra memory, no matter how long the list is. It must also leave the list exactly as it was, so the caller can still use it.

Here are some examples.

Why you cannot compare from both ends at once

With an array, you would put one index at the start and one at the end, compare, and move them towards each other. A linked list has no end index. You cannot move backwards from the last node, because each node points only forwards. Reaching the end of the list takes a full walk, and the back of the list cannot be reached in one step.

The method in this lesson solves this in four steps.

1. Find the middle of the list with two pointers that move at different speeds.
2. Reverse the second half, so the last node of the list becomes the first node of the reversed half.
3. Walk the first half and the reversed second half together, and compare values.
4. Reverse the second half again and reattach it, so the list is the same as before.

Each step uses one or two pointers and no new nodes.

Step 1: find the middle with two pointers

Start two pointers at the head. Call them slow and fast. Each step, move slow forward by one node and fast forward by two nodes. When fast reaches the end of the list, slow is at the middle.

Here is the idea with the list 1, 2, 3, 4, 5. The values are only labels, and the list has 5 nodes.

After step 2, fast is on the last node, so it cannot move two steps forward. slow is on 3, the middle of 5 nodes.

Now the list 1, 2, 3, 4, which has 4 nodes.

After step 1, fast is on 3 and there is one more node after it, but not two. The loop must stop here, so slow is on 2. With 4 nodes, the middle is the pair 2 and 3, and slow stops on the first of the pair.

The rule that works for both is this: keep moving while fast has at least two nodes ahead of it. In the code, that is written as two checks, fast->next != nullptr and fast->next->next != nullptr. The order matters. The first check makes sure fast->next is safe to use before the second check looks at fast->next->next.

Here is the loop by itself.

Node* slow = head;
Node* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
}

For a list of odd length, slow ends on the single middle node. For a list of even length, slow ends on the first of the two middle nodes. In both cases, the second half starts at slow->next. That is the rule the rest of the method relies on.

Step 2: reverse the second half

Reversing a linked list means turning each next pointer around. Walk the list once, and for each node point its next back at the node you came from. Keep three pointers: prev for the node you came from, head for the node you are on, and next to remember where to go after you turn the pointer around.

Here is the function. It reverses any list and returns the new head.

Node* reverse(Node* head) {
    Node* prev = nullptr;
    while (head != nullptr) {
        Node* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

Trace it on the list 3 -> 4, which is a second half of two nodes. We need next before changing head->next, because changing the pointer loses the way forward.

The function returns prev, which is 4. The list now reads 4 -> 3 -> nullptr.

Step 3: compare the two halves

Let secondHead be the head of the reversed second half. Walk two pointers, p from the front of the list and q from secondHead. Compare their values at each step. If any pair differs, the answer is false. If q reaches nullptr, every pair matched.

The loop stops when q runs out, not when p does. The second half is never longer than the first, because the middle node stays with the first half. For an odd-length list, the middle node is compared with nothing, which is correct. A middle value can be anything in a palindrome.

Take the list 1, 2, 3, 2, 1. After finding the middle, slow is on the 3. The second half starts at slow->next, which is 2 -> 1. Reversing it gives 1 -> 2. The comparison is:

q is now nullptr, so the loop stops with same still true.

Step 4: restore the list

The second half is now reversed, and slow->next still points at the old first node of that half, which is now the last node of the reversed chain. The list is broken until we reverse the second half again. Reverse secondHead once more and attach the result to slow.

slow->next = reverse(secondHead);

After this line the list has its original order, and its final node points to nullptr again.

This step runs even when the answer is false. If the function returned early, the caller would get a broken list. The code in the full program saves the answer in a variable called same, breaks out of the comparison loop instead of returning, and then restores the list before it returns same.

Putting the steps together

Here is the complete function. It uses the reverse function from step 2.

bool isPalindrome(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return true;
    }
 
    // Slow moves one node per step, fast moves two.
    // When fast reaches the end, slow is the last node of the first half.
    Node* slow = head;
    Node* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
 
    Node* secondHead = reverse(slow->next);
 
    bool same = true;
    Node* p = head;
    Node* q = secondHead;
    while (q != nullptr) {
        if (p->value != q->value) {
            same = false;
            break;
        }
        p = p->next;
        q = q->next;
    }
 
    // Put the second half back the way it was, whatever the answer.
    slow->next = reverse(secondHead);
    return same;
}

The first if handles lists with zero or one node. Those are always palindromes, and the rest of the function assumes at least two nodes.

Worked examples, from easy to harder

The first example is a palindrome with an even number of nodes: 7, 4, 9, 9, 4, 7. It has 6 nodes, so the middle is a pair of nodes, and the method must still split the list correctly.

Step 1 moves slow and fast as before. slow stops on the first 9, the third node. fast stops on the 4, the fifth node, because only one node is left after it and a double step is not possible. The second half starts at slow->next, which is the second 9.

Step 2 reverses the second half, 9, 4, 7, into 7, 4, 9. The list now reads 7, 4, 9, 7, 4, 9. The first three nodes are the original front half, and the next three are the reversed back half.

Step 3 compares the front half with the reversed back half. The pairs are 7 with 7, 4 with 4, and 9 with 9. All three match, so the answer is true.

Step 4 reverses the back half again, which gives 9, 4, 7 and attaches it to slow. The list reads 7, 4, 9, 9, 4, 7 again.

The second example is an odd-length list that fails: 1, 2, 5, 2, 2. It has 5 nodes, and the middle is 5.

Step 1 leaves slow on the 5, the third node. The second half is 2, 2.

Step 2 reverses 2, 2, which looks the same. The list now reads 1, 2, 5, 2, 2, with the reversed half attached.

Step 3 compares 1 with 2. The values differ, so same becomes false and the loop stops at once. The value 5 is never compared, because it belongs to the first half and the comparison stopped early.

Step 4 still runs. It reverses the back half back to the original order and attaches it. The list reads 1, 2, 5, 2, 2 again, and the function returns false.

The third example is the hardest of the three, because the middle has to be found in a longer list and the comparison goes deeper: 3, 8, 1, 6, 1, 8, 3. It has 7 nodes and is a palindrome.

Step 1 leaves slow on the middle 6 at position 4. Count from 1. The fourth node is 6, and fast ends on the last 3.

Step 2 reverses the back half, 1, 8, 3, into 3, 8, 1.

Step 3 compares the front half, 3, 8, 1 and 6, with 3, 8, 1 from the reversed half. The loop stops when the reversed half runs out, after three pairs, and the middle 6 is never compared. The answer is true.

Step 4 reverses the back half again and attaches it, so the list reads 3, 8, 1, 6, 1, 8, 3 as it did at the start.

The full program

Here is a complete program. It builds several lists, calls isPalindrome on each one, and prints the list before the call, the answer, and whether the list is unchanged. The nodes are stored in a std::vector of std::unique_ptr, so they are freed when the program ends. The lists hold raw pointers, which do not own the nodes.

The output is:

(empty)
  palindrome: yes, unchanged: yes
5
  palindrome: yes, unchanged: yes
1 -> 2
  palindrome: no, unchanged: yes
1 -> 2 -> 1
  palindrome: yes, unchanged: yes
1 -> 2 -> 2 -> 1
  palindrome: yes, unchanged: yes
1 -> 2 -> 3 -> 4 -> 2 -> 1
  palindrome: no, unchanged: yes

The last case is 1, 2, 3, 4, 2, 1. The first half ends at 3, and the second half is 4, 2, 1. Reversed, the second half is 1, 2, 4. The comparison matches 1 with 1 and 2 with 2, then finds 3 against 4 and returns false, after the list has been restored.

The program also compiles without warnings under g++ -std=c++20 -Wall -Wextra and runs clean under -fsanitize=address,undefined, which checks memory accesses and undefined arithmetic while the program runs.

Common mistakes

Leaving the list reversed. The most common mistake is to write the comparison and return without restoring the list. Here is a version that skips step 4. I ran it on the list 1, 2, 3, 4 and printed the list from the head afterwards.

Node* secondHead = reverse(slow->next);
// ... comparison loop ...
return same;  // the list is never reattached

The program printed 1 -> 2 -> 3. The node holding 4 was no longer reachable from the head. After the second half was reversed, the link from 2 still pointed at the old node 3, which now ended the list. The value 4 was still in memory, but the list no longer led to it. A caller that walks the list next would see only three values.

Checking the fast pointer in the wrong order. The loop test needs both checks, and the first must come before the second. Here is a version that reads fast->next->next directly.

while (fast->next->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
}

With the list 1, 2, 3, the first test looks at fast->next->next, which is the node 3, so the loop runs once and moves fast to 3. On the next test, fast->next is nullptr, and fast->next->next reads through a null pointer. I compiled this with g++ -std=c++20 -Wall -Wextra -fsanitize=address and ran it. The first lines of the real output were:

AddressSanitizer:DEADLYSIGNAL
==172333==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008
==172333==The signal is caused by a READ memory access.
==172333==Hint: address points to the zero page.
    #0 0x594bc1686c65 in isPalindrome(Node*) bug_loop.cpp:70

SEGV means the program tried to read memory it does not own. The address 0x8 is a small offset from nullptr. The process number and addresses will be different on your machine. The line bug_loop.cpp:70 is the loop test. The fix is to check fast->next before fast->next->next, as the full program does.

Returning early from the comparison. A return false; inside the comparison loop skips the restore step. That is why the full program uses a break and saves the answer in same. Avoid any early return between the reverse at step 2 and the restore at step 4.

Using slow as the start of the second half. Reversing from slow instead of slow->next puts the middle node into the reversed half, so the middle node is no longer in the first half. The rest of the method assumes the first half ends at slow, so the comparison and the restore step no longer match the plan. Always start the reversal at slow->next.

Practice

Exercise 1. Trace the slow and fast pointers for the list 1, 2, 3, 4, 5, 6. Give the value that slow holds at the end, and the second half that the method reverses.

Show the answer

Start with slow and fast at 1. Step 1: slow is 2, fast is 3. Step 2: slow is 3, fast is 5. Now fast->next is 6 and fast->next->next is nullptr, so the loop stops. slow holds 3. The second half starts at slow->next, which is 4, so the method reverses 4, 5, 6 and compares 1, 2, 3 against 6, 5, 4.

Exercise 2. Predict whether each list is a palindrome: 1 2 3 2 2 1, 4 9 4 9 4, and 1 1.

Show the answer

1 2 3 2 2 1 is not a palindrome. Its reverse is 1 2 2 3 2 1, which differs at the third value. 4 9 4 9 4 is a palindrome, because it reads 4 9 4 9 4 both ways. 1 1 is a palindrome. I ran all three through the same isPalindrome function in a test program and got false, true and true.

Exercise 3. Explain why the method must restore the list even when the answer is false. Name the caller's problem if it does not.

Show the answer

The caller owns the list and expects its nodes to stay in the same order. If the function returns early, the second half stays reversed, and the caller can no longer reach the nodes that were after the middle. For example, a caller that walks the list after a false answer would miss the last nodes. Restoring the list before every return keeps the function safe to call.

Exercise 4. Count the comparisons made by the comparison loop for the lists 1, 2, 2, 1 and 1, 2, 3, 2, 1. Explain why both counts are the same.

Show the answer

Both lists give 2 comparisons. For 1, 2, 2, 1, slow ends on the second node, and the reversed second half is 1, 2. The comparisons are 1 with 1, and 2 with 2. For 1, 2, 3, 2, 1, slow ends on the middle node, and the reversed second half is 1, 2. The comparisons are again 1 with 1, and 2 with 2. The middle value 3 is never compared, because the second half does not include it.

Exercise 5. Write a function bool isPalindromeCopy(Node* head) that copies the values into a std::vector<int>, then checks the vector from both ends. Use it to compare the memory cost with the method in this lesson. Say how much extra memory each one uses.

Show the answer

bool isPalindromeCopy(const Node* head) {
    std::vector<int> values;
    for (const Node* p = head; p != nullptr; p = p->next) {
        values.push_back(p->value);
    }
    for (std::size_t i = 0, j = values.size(); i + 1 < j; ++i, --j) {
        if (values[i] != values[j - 1]) {
            return false;
        }
    }
    return true;
}

The copy version stores one value for every node, so its extra memory grows with the length of the list. The method in this lesson stores only a few pointers, so its extra memory stays the same no matter how long the list is. The copy version also never changes the list, so it is simpler to write and easier to read.

Summary

• A palindrome list reads the same from the front and the back. A linked list cannot be read backwards directly, so the method reverses half of it.
• The slow and fast pointers find the middle. The second half starts at slow->next.
• Reversing a list turns each next pointer around. Save the next node before you change a pointer.
• Compare the first half with the reversed second half until the reversed half runs out.
• Reverse the second half again and reattach it, even when the answer is false, so the caller gets the list back unchanged.
• The method uses a fixed amount of extra memory, while the copy-to-array approach uses memory that grows with the list.