The O(n) Club: Palindrome Linked List—Sanity-Check Edition
⚡ TL;DR
Want to see if your singly linked list reads the same from both ends, but refuse to waste memory on an array or get caught in recursive regret? Use fast/slow pointers to hit the midpoint, reverse in place, then do a showdown compare. Java makes it almost fun:
// O(n) time, O(1) space public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode prev = null; while (slow != null) { ListNode temp = slow.next; slow.next = prev; prev = slow; slow = temp; } ListNode left = head, right = prev; while (right != null) { if (left.val != right.val) return false; left = left.next; right = right.next; } return true; }
🧠 How Devs Usually Mess This Up
One word: Arrays. You copy the list to an ArrayList, then play the two-pointer game. Works—if you enjoy igniting O(n) space when O(1) was obviously on the menu. Or maybe you dabble in recursion, thinking the call stack doesn’t count? It does. It always does. And if you reverse the second half but “forget” to restore it, you probably have a future in software sabotage.
🔍 What’s Actually Going On
Imagine a single-file line at a coffee shop (that’s your list). You want to know if the order is the same front-to-back as back-to-front—but you can only walk forwards, like a true Java developer. Step 1: Send out two runners. Fast Runner moves two steps at a time; Slow Runner one. When Fast Runner falls out of the line, Slow is dead-center. Step 2: Grab from Slow to the end and reverse those folks (no, they won’t complain). Step 3: Compare—the heads meet the tails. If it’s not the same, the list is a liar. Optional: Reset the order in case anyone else cares.
🛠️ PseudoCode
- Find the midpoint: Fast and Slow pointers; when Fast can’t move, Slow is at mid.
- Reverse second half in place:
ListNode prev = null; while (slow != null) { ListNode next = slow.next; slow.next = prev; prev = slow; slow = next; } - Compare both halves:
while (prev != null) { if (head.val != prev.val) return false; head = head.next; prev = prev.next; } - (Optional) Restore list: Reverse back again for politeness.
💻 The Code
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// Find midpoint
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
ListNode prev = null;
while (slow != null) {
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
// Compare halves
ListNode first = head, second = prev;
boolean result = true;
while (second != null) {
if (first.val != second.val) {
result = false;
break;
}
first = first.next;
second = second.next;
}
// Optional: Restore list
// ... left as exercise, interviewer’s favorite twist
return result;
}
}
⚠️ Pitfalls, Traps & Runtime Smacks
- Array and stack approaches break O(1) space—the interview vacuum will hear it!
- Did you reverse the tail, but forget to put it back? Next bug comes at you fast.
- Empty list? Palindrome by default. Single node? Absolute palindrome—yawn.
- O(n) time, real O(1) space—don’t cheat with recursion or charity arrays.
🧠 Interviewer Brain-Tattoo
Symmetry is cool—but blowing space for it isn’t. In-place or bust. Tape that to your whiteboard.
