Write a Program to check whether the Singly Linked list is a palindrome or not

The problem, simply

You get a singly linked list. Every box points only to the next box. Say true if the numbers read the same from front to back and from back to front, like 1 2 3 3 2 1 or 1 2 3 2 1. Otherwise say false.

The hard part: you cannot walk backwards. In an array you would compare the first and last slots, then move inward. In a chain there is no way to reach the last box quickly or to step back from it.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use a stack of plates to read the chain backwards.

1. Walk the chain and push every number onto a stack.
2. Walk the chain again from the head. Pop the top number each time. The stack gives the numbers back to front, so compare each box with the popped number.
3. Any mismatch means false.

import java.util.*;

class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<Integer> plates = new ArrayDeque<>();
        for (ListNode cur = head; cur != null; cur = cur.next) plates.push(cur.val);
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.val != plates.pop()) return false;   // back to front vs front to back
        }
        return true;
    }
}

How long it takes: two walks, O(n). Extra room: a stack as tall as the chain, O(n). You can push only the first half and save some room, but it is still O(n).

Way 2: the clever way

Fold the strip.

1. Find the end of the first half with two runners. slow moves one box, fast moves two. Stop when fast cannot jump two more boxes.
2. Turn the second half around, starting from slow.next, with the usual prev, curr, next flip.
3. Walk p1 from the head and p2 from the new front of the second half. Compare until p2 runs out.
4. Turn the second half back so the caller gets the chain unchanged. Then give the answer.

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {  // slow stops at the end of half one
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode back = reverse(slow.next);    // fold the second half
        boolean same = true;
        for (ListNode p1 = head, p2 = back; p2 != null; p1 = p1.next, p2 = p2.next) {
            if (p1.val != p2.val) { same = false; break; }
        }
        slow.next = reverse(back);             // unfold: leave the chain as we found it
        return same;
    }

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

How long it takes: half a walk to find the middle, half to flip, half to compare, half to flip back, so O(n). Extra room: a few fingers, O(1). For an odd chain like 1 2 3 2 1, slow stops on 3, the second half is 2 1, and the middle box is never compared, which is right.

Another way: recursion

Let the call stack do the walking backwards. A helper goes all the way to the end first. On the way back, each box compares itself with a front finger that starts at the head and moves forward one box per return.

class Solution {
    private ListNode front;

    public boolean isPalindrome(ListNode head) {
        front = head;
        return check(head);
    }

    private boolean check(ListNode node) {
        if (node == null) return true;
        if (!check(node.next)) return false;      // go to the end first
        if (node.val != front.val) return false;  // back box vs front box
        front = front.next;
        return true;
    }
}

This is short and does not change the chain, but the waiting helpers take O(n) room on the call stack, and a very long chain can overflow it.

Watch out for

• The middle search: with while (fast.next != null && fast.next.next != null), slow stops at the end of the first half for both odd and even lengths. Other versions stop one box later; then the second half starts at slow, not slow.next.
• Compare until the second half ends, not the first. The first half can be one box longer.
• Comparing Integer objects with != compares references. Compare int values, or use equals.

What interviewers ask next

• Can you do it in one walk? You can reverse the first half while slow moves, then compare the reversed first half with the rest. Still O(1) room.
• What if you may not change the list at all, even temporarily? Use the stack or recursion, O(n) room. Or copy values into an array.
• Is a doubly linked list easier? Yes. Put one finger on the head and one on the tail and move them inward.
• What if the boxes hold strings that together form a word, like "a" "bc" "cba"? Join them into one string and check that string with two fingers.

Remember this

Grown-up words: reading the same both ways is a palindrome, the two runners are fast and slow pointers, folding is reversing the second half, and the stack of plates is a stack (or the recursion call stack).