Problem overview
The method isPalindrome receives head, the first node of a singly linked list of digits, and returns true if the values read the same from the front and from the back. The list has between 1 and 100,000 nodes, and each value is between 0 and 9.
For [1, 2, 2, 1] the first and last values are both 1, and the two in the middle are both 2, so the answer is true. For [1, 2] the first value is 1 and the last is 2, so the answer is false.
Approach: make the list indexable
A palindrome check compares the first value with the last, the second with the second to last, and so on. On an array that is two indices moving toward each other. On a singly linked list it is awkward: each node knows only its successor, so there is no way to step back from the end.
The simple fix is to walk the list once and copy the values into a structure that can be read at any position, then run the two-index comparison on the copy. In Scala, ArrayBuffer is the usual growable array: appending is cheap, and reading by position is direct.
The statement's follow-up asks for O(1) extra space, which needs a different technique: find the middle, reverse the second half in place, and compare the halves. This lesson takes the simpler route and spends O(n) memory on the copy. Time is O(n) either way.
The comparison loop stops when the two indices meet or cross. Every value has then been checked against its mirror. In a list with an odd length, the middle value is its own mirror, so nothing has to be checked for it.
Step by step
- Create an empty
ArrayBuffer[Int]namedvals. The lesson uses its full name,scala.collection.mutable.ArrayBuffer, so no import is needed. Avalis enough, because the buffer object is changed but the variable is never reassigned. - Declare
curwithvar, starting athead. It walks the list and changes on every step. - Loop while
cur != null. Anulllink marks the end of the list. - Append the node's value with
vals += cur.`val`. The field is namedval, which is a keyword in Scala, so the name goes in backticks. - Advance with
cur = cur.next. Without this line the loop never ends. - Set
leftto 0. This is the index of the first value. - Set
righttovals.length - 1. This is the index of the last value. - Loop while
left < right. When the indices are equal or have crossed, there is nothing left to compare. - Return
falseon a mismatch. Ifvals(left)differs fromvals(right), the list can't be a palindrome, and one bad pair is enough. Scala reads an element with parentheses, not square brackets. - Move inward by adding 1 to
leftand subtracting 1 fromright. - End with
true. Every pair matched, and the last expression of a method is its result.
The solution in Scala
class Solution {
def isPalindrome(head: ListNode): Boolean = {
val vals = scala.collection.mutable.ArrayBuffer[Int]()
var cur = head
while (cur != null) {
vals += cur.`val`
cur = cur.next
}
var left = 0
var right = vals.length - 1
while (left < right) {
if (vals(left) != vals(right)) return false
left += 1
right -= 1
}
true
}
}
The Scala details worth a closer look:
- Backticks around
val.cur.`val`reads a field whose name is a reserved word. The backticks tell the compiler that it is an identifier. Any other field name, such asnext, needs nothing. +=on a buffer. For a mutable collection held in aval,vals += xcalls the buffer's own append and changes it in place. The same operator on an immutableListwould need avar, because it would build a new list and reassign the variable.vals(i)is a method call. Round brackets on a buffer or array callapply. An index outside0 until vals.lengththrows anIndexOutOfBoundsException. Here the loop condition keeps both indices inside the buffer.!=on Ints compares numbers. That is what we want for values, unlike the node comparison in the cycle lesson, which needs identity.return falseinside awhile. A value produced halfway through a loop can only leave the method withreturn. The plaintrueat the end is the result when the loop finishes.
Complexity
Time: O(n). The first loop visits each node once, and appending to an ArrayBuffer takes constant time on average. The second loop makes at most n / 2 comparisons.
Space: O(n). The buffer holds one value per node. That misses the follow-up's O(1) space goal. Reversing the second half of the list in place reaches it, at the cost of more pointer work and of changing the list.
Edge cases and common mistakes
- One node.
leftis 0 andrightis 0, so the loop doesn't run and the method returnstrue. A single value is a palindrome. - Even and odd lengths.
[1, 2, 2, 1]compares two pairs.[1, 2, 1]compares one pair, and the middle 2 is never compared. Usingleft <= rightwould also be correct for odd lengths, since a value equals itself, but it is not needed. - Comparing the node's value, not the node. The buffer holds
Ints, so the comparison is between numbers. Storing nodes and comparing them would compare identities and almost always answerfalse. - Forgetting
cur = cur.next. The first loop would spin forever and the buffer would grow until memory runs out. - Stopping the second loop too late. With
left != rightas the condition, an even-length list has indices that cross without ever being equal, so the loop keeps going and sooner or latervals(right)reads index -1, which throws. Useleft < right. - A mismatch at the very first pair.
[1, 2, 3, 2, 2]returnsfalse: the first value is 1 and the last is 2, so the first comparison already fails and the loop never goes further.
Testing
[1, 2, 2, 1]givestrue.[1, 2]givesfalse.[1]givestrue.[1, 2, 1]givestrue.[1, 2, 3, 2, 2]givesfalse.
