Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Palindrome Linked List

EASYProblemSolveExternal Links

Description

Given the head of a singly linked list, determine whether the values in the list form a palindrome.

A palindrome is a sequence that reads the same forwards and backwards. For example, the sequence [1, 2, 2, 1] is a palindrome because reversing it yields the same sequence.

Return true if the linked list is a palindrome, or false otherwise.

Each node in the linked list contains a single digit value and a pointer to the next node. The last node points to null.

Examples

Example 1

Input: head = [1, 2, 2, 1]

Output: true

Explanation: Reading the list from front to back gives 1 → 2 → 2 → 1. Reading it from back to front also gives 1 → 2 → 2 → 1. Since both sequences are identical, the linked list is a palindrome.

Example 2

Input: head = [1, 2]

Output: false

Explanation: Reading forward gives 1 → 2, but reading backward gives 2 → 1. These are different sequences, so the linked list is not a palindrome.

Example 3

Input: head = [1]

Output: true

Explanation: A single-element list is always a palindrome because the only element reads the same in both directions.

Constraints

  • The number of nodes in the list is in the range [1, 10^5]
  • 0 ≤ Node.val ≤ 9

Editorial

Brute Force

Intuition

The simplest way to check if a linked list is a palindrome is to collect all the node values into an array (or list), and then check whether that array reads the same forwards and backwards.

Why does this work? A linked list only lets us move forward, node by node. We cannot easily go backwards. But an array allows random access — we can compare the first element with the last, the second with the second-to-last, and so on. By converting the linked list to an array, we gain the ability to read in both directions.

Think of it like copying a sentence onto a piece of paper so you can read it both left-to-right and right-to-left, instead of trying to read a one-way conveyor belt backwards.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 2, 1]:

Step 1: Initialize an empty array to store values.

  • values = []

Step 2: Traverse the linked list and collect all values.

  • Visit node 1 → values = [1]
  • Visit node 2 → values = [1, 2]
  • Visit node 2 → values = [1, 2, 2]
  • Visit node 1 → values = [1, 2, 2, 1]

Step 3: Set two pointers: left = 0, right = 3 (last index).

Step 4: Compare values[left] and values[right]: values[0]=1 vs values[3]=1.

  • They are equal. Move left forward and right backward.
  • left = 1, right = 2

Step 5: Compare values[left] and values[right]: values[1]=2 vs values[2]=2.

  • They are equal. Move left forward and right backward.
  • left = 2, right = 1

Step 6: Now left ≥ right (left=2 > right=1), so we have checked all pairs.

  • All pairs matched → return true.

Copy to Array and Compare — Palindrome Check — Watch how we copy linked list values into an array, then use two pointers converging from both ends to verify the palindrome property.

Algorithm

  1. Traverse the linked list from head to end, collecting each node's value into an array.
  2. Initialize two pointers: left at the start (index 0), right at the end (last index).
  3. While left < right:
    • Compare values[left] with values[right].
    • If they differ, return false immediately — it is not a palindrome.
    • Otherwise, increment left and decrement right.
  4. If all pairs match, return true.

Code

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> values;
        ListNode* curr = head;
        while (curr != nullptr) {
            values.push_back(curr->val);
            curr = curr->next;
        }
        int left = 0;
        int right = values.size() - 1;
        while (left < right) {
            if (values[left] != values[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        values = []
        curr = head
        while curr:
            values.append(curr.val)
            curr = curr.next
        left, right = 0, len(values) - 1
        while left < right:
            if values[left] != values[right]:
                return False
            left += 1
            right -= 1
        return True
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            values.add(curr.val);
            curr = curr.next;
        }
        int left = 0;
        int right = values.size() - 1;
        while (left < right) {
            if (!values.get(left).equals(values.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the linked list once to collect values (O(n)), then use two pointers to compare elements, which takes at most n/2 comparisons (O(n)). Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

We store all n node values in an array. The space consumed grows linearly with the size of the linked list.

Why This Approach Is Not Efficient

While the brute force runs in O(n) time, which is already optimal in terms of time, it uses O(n) extra space to store all node values in an array.

For a linked list with 10^5 nodes, this means allocating memory for 100,000 integers. In many real-world systems and embedded environments, this extra memory is wasteful.

The follow-up challenge asks: can we check if the list is a palindrome using only O(1) extra space? The key insight is that instead of copying values out of the list, we can manipulate the list itself — specifically, reverse the second half in-place and compare it directly against the first half. This eliminates the need for any auxiliary data structure.

Better Approach - Using a Stack

Intuition

Another approach is to push all node values onto a stack, then traverse the list again while popping from the stack. Since a stack reverses the order of elements (Last-In-First-Out), popping gives us the values in reverse order. If the forward traversal and the reverse-order popping produce the same values at every position, the list is a palindrome.

Imagine stacking books one by one. The last book placed on top is the first one you remove. By comparing the removal order with the original placement order, you can detect if the sequence is a mirror image of itself.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 2, 1]:

Step 1: Initialize an empty stack.

  • stack = []

Step 2: Traverse the list and push all values onto the stack.

  • Push 1 → stack = [1]
  • Push 2 → stack = [1, 2]
  • Push 2 → stack = [1, 2, 2]
  • Push 1 → stack = [1, 2, 2, 1]

Step 3: Start a second traversal from the head. Pop from the stack and compare.

  • Node value = 1, popped value = 1 → match ✓

Step 4: Continue.

  • Node value = 2, popped value = 2 → match ✓

Step 5: Continue.

  • Node value = 2, popped value = 2 → match ✓

Step 6: Continue.

  • Node value = 1, popped value = 1 → match ✓

Step 7: All nodes processed and all values matched.

  • Return true.

Stack-Based Palindrome Check — Push All, Then Compare — Watch how we push all linked list values onto a stack, then pop them off one by one while traversing the list again. The stack reverses the order, letting us compare forward vs backward.

Algorithm

  1. Initialize an empty stack.
  2. Traverse the linked list from head to end, pushing each node's value onto the stack.
  3. Traverse the linked list again from head to end:
    • Pop the top value from the stack.
    • If it does not equal the current node's value, return false.
  4. If all values matched, return true.

Code

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> stk;
        ListNode* curr = head;
        while (curr != nullptr) {
            stk.push(curr->val);
            curr = curr->next;
        }
        curr = head;
        while (curr != nullptr) {
            if (curr->val != stk.top()) {
                return false;
            }
            stk.pop();
            curr = curr->next;
        }
        return true;
    }
};
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        stack = []
        curr = head
        while curr:
            stack.append(curr.val)
            curr = curr.next
        curr = head
        while curr:
            if curr.val != stack.pop():
                return False
            curr = curr.next
        return True
class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr.val);
            curr = curr.next;
        }
        curr = head;
        while (curr != null) {
            if (curr.val != stack.pop()) {
                return false;
            }
            curr = curr.next;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the linked list twice: once to push all values onto the stack (O(n)), and once to pop and compare (O(n)). Each push and pop operation is O(1). Total: O(n).

Space Complexity: O(n)

The stack stores all n node values. This requires O(n) additional space, similar to the array-based brute force.

Why This Approach Is Not Efficient

The stack-based approach has the same O(n) time complexity as the brute force, and it also uses O(n) extra space — the stack holds all n values just like the array did.

Fundamentally, both approaches so far copy the entire list's data into an auxiliary structure. The problem asks if we can do better on space.

The key realization is: we do not need to store the entire list to compare it. If we can find the middle of the list, reverse the second half in-place, and then compare the first half with the (now-reversed) second half node by node, we only need a few extra pointers — O(1) space. This requires two well-known linked list techniques: finding the middle with slow/fast pointers, and in-place reversal.

Optimal Approach - Reverse Second Half In-Place

Intuition

Instead of copying values, we modify the linked list itself. The strategy has three phases:

Phase 1 — Find the middle: Use the slow and fast pointer technique. The slow pointer moves one step at a time, while the fast pointer moves two steps. When fast reaches the end, slow is at the middle.

Phase 2 — Reverse the second half: Starting from the node after the middle, reverse all the remaining links in-place. Now the second half runs backwards.

Phase 3 — Compare both halves: Walk two pointers simultaneously — one from the head and one from the head of the reversed second half. If every pair of values matches, the list is a palindrome.

Imagine folding a piece of paper in half. If the top half perfectly mirrors the bottom half when you fold it, the sequence is a palindrome. Finding the middle is like finding the fold line, and reversing is like flipping the bottom half over.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 2, 1]:

Step 1: Initialize slow and fast pointers at head.

  • slow → node 0 (val=1), fast → node 0 (val=1)
  • List: 1 → 2 → 2 → 1

Step 2: Move slow one step, fast two steps.

  • slow → node 1 (val=2), fast → node 2 (val=2)

Step 3: Move slow one step, fast two steps.

  • slow → node 2 (val=2), fast → node 3 (val=1)
  • fast.next is null, so fast has reached the end. slow is at the middle boundary.

Step 4: The second half starts at slow.next. But since fast reached a non-null node (odd check), we know the list has even length. The second half is nodes [2, 1] starting from index 2.

  • Actually, slow is at index 2. We reverse from slow onward: reverse [2, 1] to get [1, 2].
  • Wait — let's be precise. slow ends at node 2 (val=2). We reverse the sublist starting at slow: 2 → 1 becomes 1 → 2.

Step 5: Now reverse the second half starting at slow.

  • Before reversal: ...→ 2 → 1 → null
  • Set prev = null, curr = slow (node at index 2, val=2)
  • curr.next=1, save next=node3(val=1), curr.next=prev(null), prev=curr(val=2), curr=next(val=1)
  • curr.next=null, save next=null, curr.next=prev(val=2), prev=curr(val=1), curr=next(null)
  • Reversed second half head = prev = node(val=1). Chain: 1 → 2 → null

Step 6: Compare first half with reversed second half.

  • p1 = head (val=1), p2 = reversed head (val=1)
  • Compare: 1 == 1 ✓

Step 7: Move both pointers forward.

  • p1 = node 1 (val=2), p2 = next (val=2)
  • Compare: 2 == 2 ✓

Step 8: p2.next is null, comparison complete.

  • All values matched → return true.

Optimal — Find Middle, Reverse Second Half, Compare — Watch the three-phase algorithm: slow/fast pointers find the middle, then the second half is reversed in-place, and finally both halves are compared node by node.

Algorithm

  1. Find the middle: Use slow and fast pointers. Move slow one step and fast two steps until fast reaches the end. Slow now points to the start of the second half.
  2. Reverse the second half: Starting from slow, reverse all links in the second half of the list using the standard iterative reversal (prev/curr/next).
  3. Compare both halves: Initialize one pointer at head and another at the head of the reversed second half. Compare values node by node.
    • If any pair differs, return false.
  4. If all pairs match, return true.
  5. (Optional) Restore the list by reversing the second half again.

Code

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }
        // Step 1: Find the middle using slow and fast pointers
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // Step 2: Reverse the second half
        ListNode* secondHalf = reverseList(slow->next);
        // Step 3: Compare both halves
        ListNode* p1 = head;
        ListNode* p2 = secondHalf;
        bool result = true;
        while (p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
                break;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return result;
    }

private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True
        # Step 1: Find the middle
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        # Step 2: Reverse the second half
        second_half = self.reverse_list(slow.next)
        # Step 3: Compare both halves
        p1, p2 = head, second_half
        while p2:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
        return True

    def reverse_list(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // Step 1: Find the middle
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // Step 2: Reverse the second half
        ListNode secondHalf = reverseList(slow.next);
        // Step 3: Compare both halves
        ListNode p1 = head;
        ListNode p2 = secondHalf;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Complexity Analysis

Time Complexity: O(n)

Finding the middle takes O(n/2) since fast moves twice as quickly. Reversing the second half takes O(n/2). Comparing both halves takes O(n/2). Total: O(n/2) + O(n/2) + O(n/2) = O(n).

Space Complexity: O(1)

We only use a constant number of extra pointers (slow, fast, prev, curr, p1, p2). No additional data structures are created. The reversal is done in-place by redirecting existing node pointers. This is the optimal space usage for this problem.