LESSON 316 OF 443 · LINKED LISTS

Palindrome Linked List in Swift: Copy to an Array, 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 Swift, explained

Problem overview

The method isPalindrome receives head, the first node of a singly linked list of digits, and returns true when the values read the same from front to back and from back to front.

For [1, 2, 2, 1] the answer is true: the first and last values match (1 and 1), and so do the two in the middle (2 and 2). For [1, 2] the answer is false, because 1 and 2 differ. A list always has at least one node, and a single node is a palindrome.

Approach: make the list indexable

Checking a palindrome means comparing the first element with the last, the second with the second to last, and so on. On an array that is easy, since you can reach both ends. A singly linked list only moves forward: each node knows its next node and nothing about the one before it, so there is no way to walk back from the tail.

The simplest fix is to copy the values into an array first, then compare from both ends toward the middle with two indices. The copy costs O(n) extra space. The follow-up asks for O(1) space, which needs a different technique (reversing the second half of the list in place); this lesson takes the array route, which is shorter and harder to get wrong.

Take [1, 2, 3, 2, 1]. The array is [1, 2, 3, 2, 1], left starts at 0 and right at 4. The pair (1, 1) matches, then (2, 2) matches. Now left and right are both 2, so the loop ends: the middle value 3 has no partner and needs no check. The method returns true.

Step by step

Create an empty array of integers, vals, with var because it grows. [Int]() is one way to write an empty array of Int.
Declare cur as a walker, starting at head. Its type is ListNode?, the same as head.
Loop while cur != nil. When the loop runs, cur has just been checked, so cur! is safe.
Append the current value to vals.
Move cur to cur!.next. After the last node this becomes nil, and the loop ends.
Set left to 0, the index of the first value.
Set right to vals.count - 1, the index of the last value.
Loop while left < right. When the indices meet or cross, every value has been compared with its mirror. An odd-length list leaves one middle value that is its own mirror.
Return false on the first mismatch. One pair of different values is enough to rule out a palindrome.
Move both indices inward: add 1 to left and subtract 1 from right.
Return true after the loop, since every pair matched.

The solution in Swift

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        var vals = [Int]()
        var cur = head
        while cur != nil {
            vals.append(cur!.val)
            cur = cur!.next
        }
        var left = 0
        var right = vals.count - 1
        while left < right {
            if vals[left] != vals[right] { return false }
            left += 1
            right -= 1
        }
        return true
    }
}

Swift details worth knowing:

Optionals and the force unwrap. cur is a ListNode?, so you can't write cur.val directly. The ! in cur!.val is safe here because the loop condition has just proved that cur isn't nil. Without that check, unwrapping nil would crash the program at run time.
Value types and reference types. vals is an array, a value type: it lives in a local variable and holds copies of the integers. cur only copies a reference to a node, so moving it never changes the list.
var versus let. vals, cur, left and right all change, so each is declared with var. Swift reports a warning for a var that never changes, which helps catch mistakes.
Integer arithmetic. vals.count - 1 is a plain Int. An Int in Swift can go negative, and the lists here are never empty, so right starts at 0 or more. Even for an empty array, right would be -1 and the loop would simply not run.

Complexity

Time: O(n). Copying the values visits each node once. The comparison loop makes at most n / 2 steps.

Space: O(n). The array holds one integer per node. This is the price of the simple approach; the in-place alternative gets this down to O(1) at the cost of changing the list while it works.

Edge cases and common mistakes

A single node. [1] gives left = 0 and right = 0, so the loop never runs and the method returns true.
Odd length. [1, 2, 1] is a palindrome. The condition left < right stops at the middle element. Using left <= right would still give the right answer, because a value always equals itself, but it does a pointless comparison.
Matching ends, different middle. [1, 2, 3, 1, 2] is not a palindrome. Stopping after the first matching pair would be wrong; every pair has to match.
Comparing counts instead of positions. [1, 2, 2, 1] and [1, 2, 1, 2] contain the same values, but only the first is a palindrome. The comparison has to pair position i with position n - 1 - i.
Walking back through the list. There is no prev pointer, so any attempt to go from the tail to the head needs the array, a stack, or reversing part of the list.

Testing

[1, 2, 2, 1] gives true, and [1, 2] gives false.
[1] gives true.
[1, 2, 1] and [1, 2, 3, 2, 1] give true.
[1, 2, 3, 1, 2], [1, 2, 1, 2] and [1, 0, 0] give false.

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

Start learning free