thesarfo

Reference

Palindrome Linked List

Checking whether a linked list's values read the same forward and backward — a stack approach vs. an O(1)-space fast/slow pointer + in-place reversal.

views 0

Check whether a singly linked list’s values read the same forward and backward — e.g. 1 → 2 → 2 → 1 and 1 → 2 → 3 → 2 → 1 are palindromes, 1 → 2 → 3 is not. (LeetCode 234)

Brute force — stack: push every value onto a stack, then walk the list again from the head comparing each node’s value against what’s popped off the stack. Readable and easy to write, but not space-efficient — still a good first solution that shows clear intent in an interview.

class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode temp = head;


        // Push all values to the stack
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }


        // Compare values while popping
        temp = head;
        while (temp != null) {
            if (temp.val != stack.pop()) {
                return false;
            }
            temp = temp.next;
        }


        return true;
    }
}

Time: O(n). Space: O(n).

Optimal — two pointers + in-place reversal (O(1) space):

  1. Find the middle using the fast/slow pointer trick (fast moves two steps, slow moves one — by the time fast reaches the end, slow is at the middle).
  2. Reverse the second half of the list starting from the middle.
  3. Compare the original first half against the reversed second half with two pointers.
  4. Optionally reverse the second half back to leave the list unchanged (not required by LeetCode, but good practice in real code).
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;


        // Step 1: Find middle using slow and fast pointers
        ListNode slow = head, 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 first and second halves
        ListNode firstHalf = head;
        ListNode secondHalf = secondHalfHead;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }


        // Optional: Restore the list
        reverse(secondHalfHead);


        return true;
    }


    // Helper function to reverse a linked list
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode nextTemp = head.next;
            head.next = prev;
            prev = head;
            head = nextTemp;
        }
        return prev;
    }
}

Time: O(n). Space: O(1). For 1 → 2 → 3 → 2 → 1: after finding the middle (node 3), reverse 2 → 1 to 1 → 2, then compare 1 → 2 → 3 against 1 → 2 (only up to where the second half ends) — all values match, so it’s a palindrome.