Palindrome Linked List

Checking whether a linked list reads the same forwards and backwards is a great warm‑up that mirrors real‑world tasks like validating undo/redo buffers or symmetric data streams. It tests your ability to manipulate list pointers and handle data in linear time and constant space.

Problem Statement

Given the head of a singly linked list, determine whether the list is a palindrome. Return true if it reads the same backwards as forwards, or false otherwise. Aim for O(n) time and O(1) extra space.

// Definition for singly-linked list:
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// Function signature in a technical interview:
public boolean isPalindrome(ListNode head);

1. Clarify Requirements Before Jumping Into Code

• Can the list be empty? An empty list counts as a palindrome.

• Single-node list? Also a palindrome.

• Values are integers; negative or positive, but exact comparison only.

• We must not modify node values; we can rewire pointers if we restore the list.

• Extra space should be constant if possible; O(n) space is allowed but not ideal.

2. Identify the Category of the Question

This is a linked-list + two-pointer problem with an added in-place reversal or stack pattern. Common linked-list patterns include:

• Two-pointer (fast/slow) to find mid

• In-place reversal of part of the list

• Dummy head for safe insertion/deletion

• Stack to store node values

• Recursion to simulate a stack

Recognizing “palindrome” suggests comparing mirrored halves, either via extra storage or by reversing half and then comparing.

3. Consider a Brute‑Force Approach to Understand the Problem

The simplest brute‑force: traverse the list, copy all values into an array or list, then use two indices to check whether values[i] == values[n-1-i] for all i.

• Time: O(n) to collect + O(n) to compare = O(n)

• Space: O(n) for the array

• Pros: Very easy to implement

• Cons: Uses O(n) extra memory

4. Brainstorm More Solutions

I’d like to reduce extra space. Options:

Stack of first half:

• Use fast/slow to find midpoint.

• Push slow’s values onto a stack while advancing fast two steps and slow one.

• Then pop from stack and compare to second half.

• Pros: O(n) time, O(n/2) space.

• Cons: Still O(n) extra space.

What if the pointers in the second half of the linked list were reversed? Then I could traverse forward from the front pointer and backwards from the back pointer until they meet.

Reverse second half in-place:

• Use fast/slow to find midpoint.

• Reverse the second half of the list in-place.

• Compare nodes from head and from reversed half one by one.

• Restore the list by reversing the second half back.

• Pros: O(n) time, O(1) space.

• Cons: Pointer manipulation more complex, must restore to avoid side effects.

Recursive two-pointer:

• Use recursion to traverse to end, compare on unwind with a front pointer.

• Pros: Elegant code.

• Cons: O(n) call stack, risk of overflow.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Copy to array + compare	O(n)	O(n)	Simple, minimal pointer logic	Extra O(n) memory
Stack of first half	O(n)	O(n/2)	Simple logic, uses built-in stack	Still O(n) extra memory
Recursive comparison	O(n)	O(n) stack	Very concise	Call stack risk, O(n) memory
Reverse second half in-place	O(n)	O(1)	True constant space, restores original list	Pointer-reversal complexity

Reverse-second-half is optimal for O(1) space.

6. Write Pseudocode to Structure Your Thoughts

function isPalindrome(head):
  if head is null or head.next is null:
    return true

  // Find midpoint
  slow = head
  fast = head
  while fast.next != null and fast.next.next != null:
    slow = slow.next
    fast = fast.next.next

  // Reverse second half
  secondHead = reverseList(slow.next)

  // Compare halves
  p1 = head
  p2 = secondHead
  result = true
  while result and p2 != null:
    if p1.val != p2.val:
      result = false
    p1 = p1.next
    p2 = p2.next

  // Restore list
  slow.next = reverseList(secondHead)

  return result

7. Consider Edge Cases

• Empty list → returns true

• Single node → returns true

• Two equal nodes → returns true

• Two different nodes → returns false

• Odd length palindrome → middle node ignored correctly

• Even length palindrome → splits evenly

• Non-palindrome → returns false quickly on mismatch

8. Write Full Code Syntax

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // 1. Find the end of first half
        ListNode firstHalfEnd = endOfFirstHalf(head);
        // 2. Reverse second half
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 3. Check palindrome
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) result = false;
            p1 = p1.next;
            p2 = p2.next;
        }

        // 4. Restore list
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

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

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Helper buildList(...) and toList(...) omitted for brevity

    // Test 1: empty list
    assert sol.isPalindrome(null) == true;

    // Test 2: single node
    assert sol.isPalindrome(buildList(1)) == true;

    // Test 3: two-node palindrome
    assert sol.isPalindrome(buildList(1,1)) == true;

    // Test 4: two-node non-palindrome
    assert sol.isPalindrome(buildList(1,2)) == false;

    // Test 5: odd-length palindrome
    assert sol.isPalindrome(buildList(1,2,3,2,1)) == true;

    // Test 6: even-length palindrome
    assert sol.isPalindrome(buildList(1,2,2,1)) == true;

    // Test 7: complex non-palindrome
    assert sol.isPalindrome(buildList(1,2,3,4,2,1)) == false;

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Fast/slow pointer finds the midpoint in one pass.

• In‑place reversal of the second half lets you compare mirrored nodes with O(1) space.

• Always restore modified data structures if the problem requires no side effects.

• Brute‑force or stack solutions clarify correctness before optimizing.

• Clear pseudocode separating phases (find mid, reverse, compare, restore) prevents pointer errors.

• Testing both odd and even lengths, as well as trivial cases, ensures full coverage.

Good Luck and Happy Coding!