Palindrome Linked List

leetcode.com

Problem Statement

Given the head of a singly linked list, return true if the linked list is a palindrome and false otherwise.

Example 1

Input:
1 -> 2 -> 2 -> 1

Output:
true

Example 2

Input:
1 -> 2

Output:
false

---

Brute Force Approach

Intuition

A singly linked list does not allow traversal from the end. To compare elements from both ends, we can first store all node values in an array and then perform a standard palindrome check using two pointers.

Interview Explanation

Since random access is not available in a linked list, I would first store all node values in an ArrayList. Once stored, I can use two pointers from the beginning and the end of the array to verify whether the sequence reads the same forward and backward.

Java Code

public boolean isPalindrome(ListNode head) {

    List<Integer> list = new ArrayList<>();

    while (head != null) {
        list.add(head.val);
        head = head.next;
    }

    int left = 0;
    int right = list.size() - 1;

    while (left < right) {

        if (!list.get(left).equals(list.get(right))) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

Complexity Analysis

Complexity	Value
Time	O(N)
Space	O(N)

---

Why Optimize?

The brute force solution uses additional space to store all node values.

Can we compare both halves without storing the entire linked list?

Yes.

If we locate the middle of the list and reverse the second half, corresponding palindrome elements become aligned and can be compared directly.

---

Optimal Approach

Key Observation

For a palindrome:

1 -> 2 -> 2 -> 1

If we reverse the second half:

First Half      Reversed Second Half

1 -> 2          1 -> 2

Both halves can now be compared node by node.

Algorithm

1. Find the middle using Slow and Fast pointers.
2. Reverse the second half of the linked list.
3. Compare the first half and reversed second half.
4. If every value matches, return true.
5. Otherwise return false.

---

Optimal Java Solution

class Solution {

    public boolean isPalindrome(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        // Find middle
        while (fast.next != null && fast.next.next != null) {

            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse second half
        ListNode secondHalf = reverseList(slow.next);

        // Compare both halves
        ListNode first = head;
        ListNode second = secondHalf;

        while (second != null) {

            if (first.val != second.val) {
                return false;
            }

            first = first.next;
            second = second.next;
        }

        return true;
    }

    public 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;
    }
}

---

Dry Run

Input

1 -> 2 -> 2 -> 1

Step 1: Find Middle

slow = 1
fast = 1

Iteration 1

slow = 2
fast = 2 (last node)

Middle:

1 -> 2 -> 2 -> 1
     ^
   slow

Step 2: Reverse Second Half

Original Second Half:

2 -> 1

After Reversal:

1 -> 2

Step 3: Compare

First Half      Second Half

1               1  ✓
2               2  ✓

All values match.

Output

true

---

Complexity Analysis

Operation	Complexity
Find Middle	O(N)
Reverse Second Half	O(N)
Compare Halves	O(N)

Total Time Complexity

O(N)

Space Complexity

O(1)

---

Pattern Recognition

Whenever you hear:

Palindrome Linked List

Think:

Find Middle
      ↓
Reverse Second Half
      ↓
Compare Both Halves

This pattern is frequently used in:

• Palindrome Linked List
• Reorder List
• Maximum Twin Sum of a Linked List
• Split Linked List Problems
• Many Slow-Fast Pointer Interview Questions

---

Interview One-Liner

I use the Slow-Fast Pointer technique to locate the middle, reverse the second half in-place, and compare both halves node by node, achieving O(N) time complexity and O(1) extra space.