Problem overview
The function isPalindrome receives the head of a singly linked list of digits (0 to 9) and returns true when the values read the same from front to back and from back to front. The list has between 1 and 100,000 nodes.
For [1, 2, 2, 1] the answer is true: the first and last values are both 1, and the middle two are both 2. For [1, 2] it is false, because 1 is not 2.
Approach: compare the front with the back by unwinding recursion
A palindrome check compares the first node with the last, the second with the second to last, and so on. With an array that is two indexes moving toward each other. A singly linked list only moves forward, so there is no way to step back from the end.
Recursion gives you the missing backward movement. If a function calls itself on node.Next before doing anything else, the calls pile up until the last node, and then they finish in reverse order: the last node first, then the one before it. While the calls unwind, you are visiting the nodes from the back.
The front still has to be walked in order, from the head. A second pointer does that: it starts at the head and moves one node forward each time a node from the back has been compared with it. The first comparison pairs the last node with the head, the second pairs the second to last with the second node, and so on.
The statement's follow-up asks for O(n) time and O(1) space. This lesson's solution is O(n) time but uses O(n) space for the recursion. The constant-space version reverses half of the list in place; this one trades the extra memory for much simpler code.
Step by step
- Declare a package-level pointer,
palindromeFront. It lives outside any function so the recursive helper can read and move it without the pointer being passed along every call. - Set it to
headat the start ofisPalindrome, so each call starts a fresh comparison from the front. - Return the result of the recursive helper, called on
head. - Declare the helper,
compareFromEnd. It takes a node and says whether the nodes from this one to the end match the same number of nodes taken from the front. - Base case: a
nilnode is past the end of the list, so there is nothing left to disagree. Returntrue. - Recurse first, then compare. Call the helper on
node.Nextand returnfalseat once if it fails. Because the call comes before any comparison, the deepest nodes are compared first. - Compare the current node with
palindromeFrontby theirValfields. - Advance
palindromeFrontto its next node, ready for the next pair as the recursion unwinds. - Return whether the values matched.
The solution in Go
var palindromeFront *ListNode
func isPalindrome(head *ListNode) bool {
palindromeFront = head
return compareFromEnd(head)
}
func compareFromEnd(node *ListNode) bool {
if node == nil {
return true
}
if !compareFromEnd(node.Next) {
return false
}
matches := node.Val == palindromeFront.Val
palindromeFront = palindromeFront.Next
return matches
}
Go details worth a closer look:
- Package-level state.
palindromeFrontis shared by every call. That is fine here becauseisPalindromeresets it before each use, but two goroutines calling the function at the same time would overwrite each other's pointer. - Pointers and
nil.*ListNodeis a pointer, andnilmarks the end of the list. Readingnode.Valthrough anilpointer panics, which is why the base case comes first. - The comparison happens before the advance.
matchesis computed from the currentpalindromeFront, which is then moved. Moving it first would compare against the wrong node and could dereferencenil. - Recursion depth. A list of 100,000 nodes means 100,000 nested calls. Go starts each goroutine with a small stack and grows it as needed, so this depth works without any special handling.
A short trace
For [1, 2, 3, 1], the calls go down to the nil after the last node. Then they return one at a time. The last node, 1, is compared with the head, 1: a match, and the front moves to 2. The node 3 is compared with 2: no match, so that call returns false. Every call above it sees the false and returns it immediately, and the result is false.
Complexity
Time: O(n). Each node is visited once on the way down and compared once on the way back.
Space: O(n). The list itself is not copied, but the recursion keeps one stack frame per node until the deepest call returns. That is what keeps this solution from meeting the O(1) follow-up.
Edge cases and common mistakes
- A single node.
[7]is a palindrome. The helper compares the node with itself, the front moves tonil, and the result istrue. - Odd length. In
[1, 2, 3, 2, 1]the middle node is compared with itself, which always matches, so it needs no special case. - Forgetting to reset the pointer. If
palindromeFrontwere set only once, a second call would start from wherever the previous call ended, and the answers would be wrong. - Advancing the front in the wrong place. Moving
palindromeFrontbefore the recursive call, or skipping the move when a pair matches, pairs the wrong nodes. - Ignoring a failed comparison. The line that returns
falseright after the recursive call is what carries a mismatch up to the top. Without it, a latertruewould overwrite an earlierfalse.
Testing
[1, 2, 2, 1]givestrue.[1, 2]givesfalse.[7]givestrue.[1, 2, 3, 2, 1]givestrue.[1, 2, 3, 4]givesfalse.
