LESSON 318 OF 445 · LINKED LISTS

Palindrome Linked List in Rust: O(n) Time by Copying to a Vec

Given the head of a singly linked list, return true if it is a palindrome, or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

The number of nodes in the list is in the range [1, 10⁵].
0 <= Node.val <= 9

Follow up: This lesson's solution uses O(n) extra space: it stores the list's values (or, in a recursive version, keeps one call per node on the stack). As an extra challenge beyond this lesson, could you do it in O(n) time and O(1) extra space?

STEP 1 OF 9

Guided

Ctrl + Enter to check

RUST · LINKED LISTS

Palindrome Linked List in Rust, explained

Problem overview

The function is_palindrome receives the head of a singly linked list, an Option<Box<ListNode>>, and returns true if the values read the same from both ends. Each node holds a val from 0 to 9 and a next link. The list has between 1 and 100,000 nodes.

For [1, 2, 2, 1] the answer is true. For [1, 2] it is false, because the first value is 1 and the last is 2.

Approach: copy the values, then compare from both ends

A singly linked list only moves forward. There is no way to step back from the tail, so comparing the last node with the first is awkward. An array has no such limit: you can read index i and index n - 1 - i directly.

So the solution walks the list once and copies every value into a Vec. Then it compares the mirror pairs: the first with the last, the second with the second to last, and so on. It only needs to check the first half, because each pair is checked from its left member. A middle element in an odd-length list pairs with itself and needs no check.

This costs O(n) time and O(n) extra space. The follow-up in the statement asks for O(1) space, which is possible by reversing the second half of the list in place and comparing the halves. This lesson takes the simpler route.

Step by step

Create vals, an empty mutable Vec<i32>.
Take ownership of the list in a mutable variable curr, since the loop will move it forward.
Walk the list with while let Some(mut node) = curr. The loop ends when curr is None.
Record and advance. Push node.val onto vals, then set curr to node.next.take().
Store the length in n.
Loop i over 0..n / 2, the first half.
Check each pair: does vals[i] differ from its mirror vals[n - 1 - i]?
Return false at the first mismatch.
Return true if the loop ends with no mismatch.

The solution in Rust

impl Solution {
    fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
        let mut vals: Vec<i32> = Vec::new();
        let mut curr = head;
        while let Some(mut node) = curr {
            vals.push(node.val);
            curr = node.next.take();
        }
        let n = vals.len();
        for i in 0..n / 2 {
            if vals[i] != vals[n - 1 - i] {
                return false;
            }
        }
        true
    }
}

The Rust details worth a look:

while let Some(mut node) = curr moves the node out. A Box<ListNode> owns its node, and the pattern takes that box out of curr, leaving curr unusable until it is assigned again. The assignment on the next line does that. mut is needed on node because take() changes it.
node.next.take() replaces node.next with None and returns the old value, so the rest of the list moves into curr without any copying. The node is left with no next and is dropped at the end of the iteration.
Why that matters for long lists. Dropping a long chain of boxes drops one node, then the next inside it, and so on, which recurses once per node. Taking the links apart means each node is dropped on its own, so a list of 100,000 nodes doesn't pile up drop calls.
0..n / 2 uses integer division: for n = 5 it covers indexes 0 and 1, and the middle index 2 is skipped. For n = 1 the range is empty, so a single node is a palindrome.
n - 1 - i is safe on a usize, because n is at least 1 whenever the loop body runs, and i is below n / 2. Vectors check their indexes, so a wrong index would panic rather than read garbage.
true without a semicolon is the value of the function when no return fires.

The O(1)-space idea, in brief

The follow-up reaches constant space with three steps on the list itself. First, find the middle with two pointers, one moving a node at a time and one moving two. Second, reverse the second half in place, by pointing each node's next at the node before it. Third, walk the first half and the reversed second half together and compare values. In Rust this means juggling ownership of the links with take() at every move, which is why the copy-to-a-vector version is the clearer first solution. It also changes the list, so a careful version restores it afterwards.

Complexity

Time: O(n). One pass copies the values and a second pass of up to n / 2 comparisons checks them.

Space: O(n). The vector holds one i32 per node. This is more than the follow-up's O(1), which needs the in-place reversal of the second half.

Edge cases and common mistakes

One node. [1] gives true. The comparison loop doesn't run.
Odd length. [1, 2, 1] gives true. The middle value has no partner and isn't compared.
Even length with a bad pair. [1, 2, 2, 3] returns false at the first pair, 1 against 3.
Almost a palindrome. [1, 2, 3, 2, 2] gives false: the second pair is 2 against 2, but the first pair, 1 against 2, already fails. Comparing only the number of each digit would wrongly accept lists with the same counts in a different order.
Looping over the whole vector. Comparing every index to its mirror works too, but it repeats each pair twice.
Comparing neighbours. A palindrome has nothing to do with equal adjacent values: [1, 2, 1] has none, and [1, 1, 2] has one but isn't a palindrome.

Testing

[1, 2, 2, 1] gives true.
[1, 2] gives false.
[1] gives true.
[1, 2, 1] gives true.
[1, 2, 3, 2, 2] gives false.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free