Cracking The Coding Interview Together – Problem 2.6: Palindrome

I hope you’re doing well and still enjoying this series. If you’ve been following along, you already know the drill by now. We don’t jump straight into code. We slow down, understand the problem, ask the right questions, and then build our solution step by step — exactly the way you’d do it sitting across an interviewer.

Today’s problem looks innocent at first glance. But as usual, there’s more hiding underneath.

Let’s get into it.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Palindrome: Implement a function to check if a linked list is a palindrome

Analyse the problem statement together

Before we think about code, let’s make sure we agree on what this means.

A palindrome is something that reads the same forwards and backwards.

Examples with strings:

• "racecar" → palindrome
• "abba" → palindrome
• "hello" → not a palindrome

Now apply that idea to a linked list.

If the linked list is:

Input

1 → 2 → 3 → 2 → 1

This is a palindrome.

If the linked list is:

1 → 2 → 3 → 4

This is not a palindrome.

So effectively, the values from the head moving forward should match the values from the tail moving backward.

Sounds simple, right?
But here’s the catch: linked lists don’t let you move backward.

And that’s where the interview really begins.

Questions for the interviewer

Before jumping into solutions, this is the moment where you pause and ask clarifying questions. Interviewers love this part because it shows how you think.

Here are the questions I would ask:

1. Can the linked list be empty?
2. Can it contain just one node?
3. Are we allowed to modify the linked list?
4. Do we care about extra space usage, or is any solution acceptable?
5. What kind of linked list is it — singly or doubly?

Most likely, you’ll hear answers like:

• Yes, the list can be empty.
• Yes, a single-node list should be considered a palindrome.
• It’s a singly linked list.
• Extra space is allowed, but a more optimal solution is preferred.
• Try not to modify the list permanently.

Now we have constraints. And constraints shape solutions.

Think about the Solution

This is the part most candidates rush through. Don’t.

Ask yourself:

• If this were an array, how would I solve it?
• What makes a linked list harder here?
• What information do I not have direct access to?

If this were an array, we’d simply use two pointers:

• One from the start
• One from the end
• Compare values until they meet

But in a singly linked list, there’s no easy way to go backward.

So we need to get creative.

Let’s explore our options.

Approach 1: Convert Linked List to Array (Brute Force)

The simplest idea is:

1. Traverse the linked list
2. Store all values in an array or list
3. Use two pointers on the array to check for palindrome

This works. It’s easy to implement. And it’s totally acceptable as a first answer in an interview.

But it uses extra space.

Let’s analyze it:

• Time Complexity: O(n)
• Space Complexity: O(n)

Good starting point. But interviewers usually ask:

Can you do better?

Let’s keep going.

Approach 2: Reverse the Entire Linked List

Another idea:

1. Reverse the linked list
2. Compare the original and reversed list node by node

This sounds clever, but it comes with a problem:

• You’re modifying the list
• You either need to restore it or risk side effects

You can do it, but it’s messy and error-prone under interview pressure.

We can do better.

Approach 3: Reverse Only the Second Half (Preferred)

This is the approach most interviewers are hoping you reach.

The idea is simple once you see it:

1. Find the middle of the linked list
2. Reverse the second half
3. Compare the first half with the reversed second half
4. (Optional but good practice) Restore the list

Let’s break this down slowly.

Finding the Middle of the Linked List

We use the classic slow and fast pointer technique.

• Slow pointer moves one step at a time
• Fast pointer moves two steps at a time

When the fast pointer reaches the end:

• Slow pointer will be at the middle

This works for:

• Even-length lists
• Odd-length lists

If the list has odd length, we can skip the middle element — it doesn’t affect palindrome symmetry.

Reversing the Second Half

Once we reach the middle:

• Reverse the linked list starting from the slow pointer
• This gives us a new head for the second half

Now we have:

• First half starting from the original head
• Second half starting from the reversed list

Comparing Both Halves

Now it’s simple:

• Move both pointers forward together
• Compare values at each step
• If any mismatch occurs → not a palindrome

If all values match → it is a palindrome.

Write code and explain

Now let’s translate this idea into code.

Java code

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class PalindromeLinkedList {

    public static 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 != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse second half
        ListNode secondHalfHead = reverse(slow);

        // Step 3: Compare both halves
        ListNode firstHalf = head;
        ListNode secondHalf = secondHalfHead;

        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true;
    }

    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }

        return prev;
    }
}

Walk the Interviewer Through the Code

Here’s how I would explain it out loud:

• First, I handle trivial cases like empty or single-node lists.
• Then I use slow and fast pointers to locate the middle.
• I reverse the second half of the list starting from the middle.
• I compare nodes from the start and from the reversed second half.
• If all values match, the list is a palindrome.

Clear. Logical. No surprises.

Time & Space Complexity

Time Complexity

• Finding middle: O(n)
• Reversing second half: O(n)
• Comparing halves: O(n)

Overall: O(n)

Space Complexity

• No extra data structures
• Only pointers used

Overall: O(1)

Final Thoughts

This problem is a great example of why linked lists show up so often in interviews.

It’s not about memorizing tricks.
It’s about understanding constraints and adapting familiar ideas to new structures.

If you reached the reverse-second-half solution on your own — well done.
If not, that’s perfectly fine. That’s why we practice.

As always, take some time to re-read the code, maybe draw it on paper, and try explaining it out loud. That habit alone will set you apart in real interviews.

I’ll see you in the next one.

Until then — happy coding 👋