LESSON 315 OF 442 · LINKED LISTS

Palindrome Linked List in Kotlin: Copy to a List, Two Indices

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 Kotlin, explained

Problem overview

The function isPalindrome receives head, the first node of a singly linked list, and returns true if the values read the same from front to back and from back to front. Each node holds a digit from 0 to 9, and the list has at least one node.

For [1, 2, 2, 1] the answer is true: the first and last values match, and so do the two in the middle. For [1, 2] the answer is false, because 1 and 2 differ.

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 toward the middle. That is easy with an array, where any position can be read directly. A singly linked list is the problem: each node knows only the node after it, so there is no way to start at the tail and step backward.

The lesson's fix is to walk the list once and copy its values into an ArrayList. After that, two indices, one at each end, move toward each other while comparing values. The first mismatch proves the list is not a palindrome. If the indices meet without a mismatch, it is one.

The statement also asks, as a follow-up, for O(n) time and O(1) space. This lesson's copy needs O(n) extra space, so it doesn't meet that follow-up. The usual way to reach it is to reverse the second half of the list in place and compare the two halves. This lesson keeps to the simpler approach, which is easier to get right.

Step by step

Create vals, an empty ArrayList<Int>, with val. The variable never points to a different list, only the list's contents change.
Declare cur with var and start it at head. It walks the nodes, and its type is ListNode? like head.
Loop while cur != null. Inside the loop Kotlin treats cur as non-null (a smart cast), so its fields can be read directly.
Add the node's value to vals. The field is called val, which is also a Kotlin keyword, so it must be written with backticks: cur.`val`.
Move cur to cur.next. After the last node, next is null and the loop ends.
Set left to 0, the index of the first value.
Set right to vals.size - 1, the index of the last value.
Loop while left < right. When the indices meet or cross, every value has met its mirror. In an odd-length list the middle value has no partner, and it needs no check.
Return false on a mismatch. If vals[left] differs from vals[right], one bad pair is enough.
Move the indices inward: add 1 to left and subtract 1 from right.
Return true after the loop. Every pair matched.

The solution in Kotlin

class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        val vals = ArrayList<Int>()
        var cur = head
        while (cur != null) {
            vals.add(cur.`val`)
            cur = cur.next
        }
        var left = 0
        var right = vals.size - 1
        while (left < right) {
            if (vals[left] != vals[right]) return false
            left += 1
            right -= 1
        }
        return true
    }
}

The Kotlin details worth a closer look:

Backticks around val. A name that is a keyword can still be used as an identifier if it is wrapped in backticks. cur.val without them is a syntax error.
ArrayList<Int> in Kotlin. ArrayList is available without an import and is a MutableList<Int> (on the JVM it is Java's ArrayList). It holds boxed Int objects, so there is some memory overhead compared with an IntArray.
vals[left] and !=. The square brackets call get. The != operator compares the contents of the two values, with equals behind it, which for Int is a plain numeric comparison. In Kotlin you don't need a method like Java's equals for this.
Smart cast on cur. After cur != null succeeds, cur.`val` and cur.next compile without ?. because cur is a local var that nothing changes between the check and its use.
left += 1. This changes the var. left++ and left-- are also valid Kotlin statements.

Complexity

Time: O(n). The first loop visits each node once. The second loop moves two indices toward each other and runs about n / 2 times.

Space: O(n). vals holds one entry for each node. This is the price of reading the list from both ends.

Edge cases and common mistakes

A single node. left and right are both 0, so the loop doesn't run and the function returns true. A single value reads the same in both directions.
Odd length. In [1, 2, 3, 2, 1] the loop stops when both indices stand on the 3. Using left <= right would compare the 3 with itself, which is harmless but unnecessary.
Mismatch near the middle. [1, 2, 3, 4, 1] matches at the ends and then fails on 2 against 4, so a check of only the first and last values is not enough.
Wrong side of the palindrome. [1, 0, 0] returns false: the first value 1 is compared with the last, 0, and fails at once.
Comparing nodes instead of values. Comparing nodes themselves would never match, because each node is a distinct object. Compare the stored values.
Forgetting to advance cur. Without cur = cur.next, the first loop adds the head's value forever.

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.

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

Start learning free