LESSON 315 OF 442 · LINKED LISTS

Palindrome Linked List in TypeScript: Copy to an Array, Compare Ends

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 11

Guided

Ctrl + Enter to check

Palindrome Linked List in TypeScript, explained

Problem overview

The method isPalindrome receives the head of a singly linked list of digits and returns true if the values read the same from front to back and from back to front.

For [1, 2, 2, 1] the first value matches the last and the second matches the third, so the answer is true. For [1, 2] the first value is 1 and the last is 2, so the answer is false. The list has at least one node, and every value is between 0 and 9.

Approach: make the list indexable

Checking a palindrome means comparing the first element with the last, the second with the second to last, and so on. An array makes that easy, because any position can be read directly. A singly linked list can't do it: each node knows only the one after it, so there is no way to step backwards from the tail.

So the lesson copies the values into an array first, then compares from both ends with two indices that move toward the middle. When the indices meet or cross, every value has been compared with its mirror.

Building the array costs one pass over the list and the comparison costs another half pass, so the work is linear. What the array costs is memory: one slot for every node.

The statement's follow-up asks for O(1) extra space, which needs a different technique: reverse the second half of the list in place and compare the halves. This lesson's array approach is simpler and uses O(n) space.

Step by step

Create vals as a const typed number[], starting empty. It is const because the variable never points at a different array, even though the array's contents grow.
Create cur, typed ListNode | null, starting at head. It walks the list.
Loop while cur !== null. The list ends at a null pointer, so that is the stopping condition.
Push cur.val onto vals inside the loop.
Advance cur to cur.next. Forgetting this line makes the loop run forever.
Set left to 0, the first index.
Set right to vals.length - 1, the last index.
Loop while left < right. Once the indices meet, the remaining value, if any, is the middle of an odd-length list. It has no partner, so it needs no check.
Return false on the first mismatch. One unequal pair is enough to rule out a palindrome.
Move the indices inward: add 1 to left and subtract 1 from right.
Return true after the loop. Every pair matched.

The solution in TypeScript

class Solution {
    isPalindrome(head: ListNode | null): boolean {
        const vals: number[] = [];
        let cur: ListNode | null = head;
        while (cur !== null) {
            vals.push(cur.val);
            cur = cur.next;
        }
        let left: number = 0;
        let right: number = vals.length - 1;
        while (left < right) {
            if (vals[left] !== vals[right]) return false;
            left += 1;
            right -= 1;
        }
        return true;
    }
}

Some TypeScript points about this code:

const protects the binding, not the contents. vals.push(...) is allowed on a const array. Only an assignment such as vals = [] would be an error.
The annotations are optional. left: number = 0 means the same as let left = 0, since TypeScript infers number. They are written out here for practice, and they disappear when the code is compiled to JavaScript.
Numbers compare with !== by value. Unlike nodes, which compare by reference, two number values compare equal whenever they hold the same number. That is why vals[left] !== vals[right] is the right test for values. Comparing the nodes themselves would never match, since every node is a distinct object.
No negative index problem. The list has at least one node, so vals.length - 1 is at least 0. If the list could be empty, right would be -1 and the loop would simply not run, returning true.

Complexity

Time: O(n). The first loop visits each node once, and the second loop makes at most n / 2 comparisons.

Space: O(n). The array holds one number for every node. This misses the follow-up's O(1) space target, but it has the same linear time.

Edge cases and common mistakes

A single node. [7] gives left = 0 and right = 0, the loop doesn't run, and the answer is true.
Odd length. [1, 2, 3, 2, 1] compares the 1s, then the 2s, then stops with both indices on 3. The answer is true.
Mismatch deep inside. [1, 2, 3, 4, 1] matches the 1s, then compares 2 with 4 and returns false.
Using left <= right. It also works, because the middle value would be compared with itself, but it does one useless comparison.
Letting the indices cross. With a condition such as left < vals.length, right eventually goes below 0, and vals[-1] is undefined, which never equals a digit. A palindrome would then be reported as false.
Comparing nodes instead of val. Pushing cur instead of cur.val would make the equality checks compare objects, and almost every list would be called a non-palindrome.
Reversing in place and forgetting to restore. If you solve the follow-up and reverse half of the list, the caller's list is changed unless you reverse it back.

Testing

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

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

Start learning free