# How to Detect if a Linked List Is a Palindrome: Two Optimal Approaches > Detect if a linked list is a palindrome using recursion or fast/slow pointers. Explore O(N) time and O(1) space solutions for this common algorithm problem. - Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm) - Tags: how-to-guide - Published: 2026-02-25 --- **You can detect if a linked list is a palindrome in O(N) time by either using recursion to simulate a stack (O(N) space) or using a fast/slow pointer to find the middle and reversing the second half in place (O(1) space).** Unlike arrays or strings, a singly-linked list cannot be traversed backwards, which prevents the classic two-pointer technique from working directly. According to the `labuladong/fucking-algorithm` repository, specifically the tutorial in `高频面试系列/判断回文链表.md`, there are two robust strategies that overcome this limitation while maintaining linear time complexity. ## Why the Standard Two-Pointer Technique Fails In a singly-linked list, each node only stores a reference to the `next` node. This means you cannot start one pointer at the head and another at the tail and move them toward the center. Any solution must either use extra space to store the values (or nodes) in reverse order, or temporarily modify the list structure to allow backward traversal. ## Method 1: Recursive Stack Simulation (O(N) Time, O(N) Space) This approach leverages the program call stack to implicitly reverse the list. As explained in lines 121-151 of `高频面试系列/判断回文链表.md`, the algorithm uses post-order traversal to compare nodes from the outside in. ### How It Works The recursion first reaches the tail of the list (the base case). As the stack unwinds, each recursive call holds a reference to a node from the second half of the list (`right`), while a global pointer (`left`) starts at the head and moves forward. The algorithm compares `left.val` with `right.val` at each unwinding step. If any pair differs, the list is not a palindrome. ### Implementation Details The solution requires a class-level variable `left` to track the front of the list and a boolean `res` to store the result. The `traverse` method implements the post-order logic: it recurses on `right.next` first, then performs the comparison, then advances `left`. ```python class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def __init__(self): self.left = None self.is_pal = True def isPalindrome(self, head: ListNode) -> bool: self.left = head self._traverse(head) return self.is_pal def _traverse(self, right: ListNode): if not right: return self._traverse(right.next) # reach the tail first if self.left.val != right.val: # compare mirrored nodes self.is_pal = False self.left = self.left.next # advance left pointer ``` This method is conceptually identical to pushing all nodes onto an explicit stack and then popping them to compare with the original list, but it uses the system's call stack instead of auxiliary data structures. ## Method 2: Fast/Slow Pointer with In-Place Reversal (O(N) Time, O(1) Space) For scenarios where space is constrained, the optimal solution uses the **fast/slow pointer** technique to find the middle of the list, then reverses the second half in place. This allows you to compare the first half with the reversed second half using two forward-moving pointers. As documented in lines 168-199 of `高频面试系列/判断回文链表.md`, this approach achieves O(1) extra space complexity. ### Step-by-Step Algorithm 1. **Locate the midpoint**: Initialize `slow` and `fast` at the head. Move `fast` two steps and `slow` one step per iteration. When `fast` reaches the end, `slow` points to the start of the second half. 2. **Handle odd length**: If `fast` is not null (odd number of nodes), move `slow` one step forward to skip the exact middle node. 3. **Reverse the second half**: Reverse the sub-list starting at `slow` using a standard iterative reversal. 4. **Compare both halves**: Initialize `left` at the head and `right` at the new head of the reversed half. Walk both pointers simultaneously, comparing values. 5. **Restore the list (optional)**: Reverse the second half again to restore the original structure. ### Implementation Details The `reverse` helper function uses three pointers (`prev`, `node`, `nxt`) to flip the `next` references iteratively. The main `isPalindrome` method orchestrates the pointer movements and comparison logic. ```java class ListNode { int val; ListNode next; ListNode(int v) { val = v; } } class Solution { // Checks if the linked list is a palindrome. public boolean isPalindrome(ListNode head) { if (head == null) return true; // 1. Find the middle (slow will point to start of second half) ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 2. Skip the middle node for odd length lists if (fast != null) { // odd number of nodes slow = slow.next; } // 3. Reverse the second half ListNode right = reverse(slow); ListNode left = head; // 4. Compare both halves while (right != null) { if (left.val != right.val) return false; left = left.next; right = right.next; } // (Optional) 5. Restore the original list order by reversing again // reverse(slow); return true; } // Helper: reverses a singly‑linked list and returns the new head private ListNode reverse(ListNode node) { ListNode prev = null; while (node != null) { ListNode nxt = node.next; node.next = prev; prev = node; node = nxt; } return prev; } } ``` This approach is preferred in production code and technical interviews when the problem constraints require O(1) auxiliary space, as it only uses a constant number of pointer variables regardless of list length. ## Summary - **Singly-linked lists** cannot be traversed backwards, preventing the standard two-pointer palindrome check used for arrays. - **Recursive stack simulation** achieves O(N) time by using the call stack to reverse the list implicitly, requiring O(N) space. This is implemented in `高频面试系列/判断回文链表.md` lines 121-151. - **Fast/slow pointer with in-place reversal** achieves optimal O(N) time and O(1) space by finding the middle, reversing the second half, comparing, and optionally restoring the list. This is detailed in lines 168-199 of the same file. - Both solutions rely on the symmetry property of palindromes: the first half must mirror the second half exactly. ## Frequently Asked Questions ### Can I solve this by converting the linked list to an array? Yes, you can traverse the list once to copy values into an array or ArrayList, then use standard two-pointer techniques on the array. This approach runs in O(N) time but requires O(N) extra space for the array, making it less optimal than the in-place reversal method for space-constrained environments. ### Why not just use a stack explicitly instead of recursion? An explicit stack data structure works perfectly well and follows the same logic as the recursive approach: push all nodes onto the stack, then pop and compare with the original list. However, the recursive solution is often more concise in languages like Python, while the explicit stack version requires additional boilerplate to manage the data structure. Both use O(N) auxiliary space. ### Does the fast/slow pointer method modify the original list permanently? The algorithm temporarily reverses the second half of the list to enable the comparison, which does modify the `next` pointers. However, as shown in the Java implementation, you can restore the original order by reversing the second half a second time after the comparison is complete. If you omit this restoration step, the list will remain modified (reversed in the second half). ### What is the time complexity of the recursive approach? The recursive approach runs in **O(N)** time because it visits each node exactly twice: once during the forward recursion to reach the tail, and once during the unwinding phase to perform comparisons. The space complexity is also **O(N)** due to the call stack depth equaling the length of the list.