LESSON 314 OF 441 · LINKED LISTS

Palindrome Linked List in C#: Recursion with a Front Cursor

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

C# · LINKED LISTS

Palindrome Linked List in C#, explained

Problem overview

The method IsPalindrome receives the head of a singly linked list of ListNode objects, each holding an int in val. It returns true if the values read the same from the front and from the back, and false otherwise.

The list [1, 2, 2, 1] is a palindrome: the first and last values are both 1, the middle two are both 2. The list [1, 2] is not, because 1 differs from 2. A one-node list is always a palindrome.

An array would make this easy, with one index moving up from 0 and another moving down from the end. A singly linked list has no way to step backwards, so the lesson needs another way to look at the nodes from the back.

Approach: let the call stack walk backwards

A recursive call remembers where it came from. If a method calls itself on t1.next before doing anything else, the first call to finish is the one on the last node, then the one on the second to last, and so on. The calls return in reverse order, which is exactly the backwards walk the list can't do by itself.

So the plan has two cursors:

The back cursor is the argument t1 of the recursive method. While the calls unwind, it visits the nodes from the last to the first.
The front cursor is a field named temp. It starts at head and moves one node forward after every comparison.

When the call for the last node finishes its recursion, temp is still on the first node, so they get compared. Then temp moves to the second node, the call for the second-to-last node resumes, and they get compared, and so on.

Here is [1, 2, 3, 2, 1]. The comparisons happen in this order:

Comparison	Back node (`t1`)	Front node (`temp`)	Equal?
1	5th node (1)	1st node (1)	yes
2	4th node (2)	2nd node (2)	yes
3	3rd node (3)	3rd node (3)	yes
4	2nd node (2)	4th node (2)	yes
5	1st node (1)	5th node (1)	yes

Every pair is checked twice, once from each side, so the second half of the work repeats the first. It is harmless, and it keeps the code short.

Step by step

Declare a field temp of type ListNode. The front cursor has to survive from one recursive call to the next, so it lives in the object and not in a local variable.
Point temp at head at the start of IsPalindrome. Setting it on every call means the same Solution object can be used for several lists.
Return the result of the helper, GiveNode(head).
Declare the helper GiveNode. It takes the current node and returns a bool. It is private because it's only a tool of this class.
Base case. When the node is null, we are past the tail and nothing is left to compare, so the answer is true.
Recurse first. Call GiveNode(t1.next) before touching the current node. If a deeper pair already failed, pass false up and stop.
Compare the values of the back node and the front node.
Advance temp by one node, ready for the next comparison on the way out.
Return the comparison result of this pair.

The solution in C#

class Solution {
    ListNode temp;

    public bool IsPalindrome(ListNode head) {
        temp = head;
        return GiveNode(head);
    }

    private bool GiveNode(ListNode t1) {
        if (t1 == null)
        return true;
        if(!GiveNode(t1.next))
        return false;
        bool b = t1.val == temp.val;
        temp = temp.next;
        return b;
    }
}

The C# details worth knowing:

Fields default to null. ListNode temp; is a reference-type field, so it starts as null without any assignment. The first line of IsPalindrome sets it before the helper reads it.
Braceless if. if (t1 == null) followed by return true; on the next line works because an if controls the single statement after it. Indentation means nothing to the compiler, so adding a second statement without braces would not be part of the if.
Integers compare by value. t1.val == temp.val compares two ints, which is what we want. Comparing t1 == temp would compare the nodes as references.
Why temp is never null when it is read. The comparison for a node runs after the calls for all the nodes behind it, and each of those moved temp forward once. So temp has moved fewer than n times and still points at a real node.

Complexity

Let n be the number of nodes.

Time: O(n). The method makes one recursive call per node, and each call does a constant amount of work.

Space: O(n). The calls are all open at the same time when the recursion reaches the tail, so the call stack holds n frames. A list of 100,000 nodes, the largest the constraints allow, runs fine in C# on .NET 8, but this is not the constant-memory solution that the follow-up asks for. That one finds the middle of the list with two pointers, reverses the second half in place, compares the halves and, if needed, reverses it back. This lesson trades the memory for much simpler code.

Edge cases and common mistakes

One node. The call for the node recurses into null, gets true, compares the node with itself and returns true.
Two equal nodes. [7, 7] returns true, and [1, 2] returns false.
Odd length. In [1, 2, 1] the middle node is compared with itself, which is fine. [1, 2, 3, 4, 1] returns false because 4 differs from 2.
Same ends, different middle. [1, 2, 1, 1] returns false. Checking only the first and last values is not enough.
Forgetting to advance temp. Every comparison would use the first node's value, and lists like [1, 2, 1] would be judged wrongly.
Advancing temp before the recursive call. The front cursor would move in the wrong order and drift away from the back cursor.
Using a local instead of a field. A local temp would be a separate copy in every call, so the move forward would be lost as soon as the call returned.

Testing

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

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

Start learning free