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
t1of 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 atheadand 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
tempof typeListNode. 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
tempatheadat the start ofIsPalindrome. Setting it on every call means the sameSolutionobject 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 abool. It isprivatebecause 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 istrue. - Recurse first. Call
GiveNode(t1.next)before touching the current node. If a deeper pair already failed, passfalseup and stop. - Compare the values of the back node and the front node.
- Advance
tempby 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 asnullwithout any assignment. The first line ofIsPalindromesets it before the helper reads it. - Braceless
if.if (t1 == null)followed byreturn true;on the next line works because anifcontrols the single statement after it. Indentation means nothing to the compiler, so adding a second statement without braces would not be part of theif. - Integers compare by value.
t1.val == temp.valcompares twoints, which is what we want. Comparingt1 == tempwould compare the nodes as references. - Why
tempis nevernullwhen it is read. The comparison for a node runs after the calls for all the nodes behind it, and each of those movedtempforward once. Sotemphas moved fewer thanntimes 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, getstrue, compares the node with itself and returnstrue. - Two equal nodes.
[7, 7]returnstrue, and[1, 2]returnsfalse. - Odd length. In
[1, 2, 1]the middle node is compared with itself, which is fine.[1, 2, 3, 4, 1]returnsfalsebecause 4 differs from 2. - Same ends, different middle.
[1, 2, 1, 1]returnsfalse. 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
tempbefore 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
tempwould 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]givestrue.[1, 2]givesfalse.[1]givestrue.[1, 2, 3, 2, 1]givestrue.[1, 2, 3, 4, 1]givesfalse.[1, 2, 1, 1]givesfalse.
