Check if Linked List is Palindrome
Determine if a singly linked list reads the same forwards and backwards (palindrome property). The optimal O(n) time, O(1) space solution involves: (1) finding the middle using Floyd's slow/fast pointers, (2) reversing the second half, (3) comparing both halves node-by-node. This problem elegantly combines multiple linked list techniques and is commonly asked in technical interviews.
Visualization
Interactive visualization for Check if Linked List is Palindrome
Interactive visualization with step-by-step execution
Implementation
1function isPalindrome(head: ListNode | null): boolean {
2 if (!head || !head.next) return true;
3
4 // Find middle using slow/fast pointers
5 let slow = head;
6 let fast = head;
7
8 while (fast.next && fast.next.next) {
9 slow = slow.next!;
10 fast = fast.next.next;
11 }
12
13 // Reverse second half
14 let secondHalf = reverseList(slow.next);
15 slow.next = null;
16
17 // Compare both halves
18 let p1 = head;
19 let p2 = secondHalf;
20
21 while (p2) {
22 if (p1.val !== p2.val) return false;
23 p1 = p1.next!;
24 p2 = p2.next;
25 }
26
27 return true;
28}
29
30function reverseList(head: ListNode | null): ListNode | null {
31 let prev = null;
32 let curr = head;
33
34 while (curr) {
35 const next = curr.next;
36 curr.next = prev;
37 prev = curr;
38 curr = next;
39 }
40
41 return prev;
42}Deep Dive
Theoretical Foundation
Palindrome checking requires comparing first half with second half reversed. For linked lists without random access, we use three steps: (1) Find middle with Floyd's algorithm (slow moves 1 step, fast moves 2). (2) Reverse second half in-place. (3) Compare first half with reversed second half. If all values match, it's a palindrome. Time: O(n) single pass. Space: O(1) in-place. Alternative: use stack to store first half (O(n) space) or recursion (O(n) call stack).
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Data validation (symmetric structures)
String/sequence palindrome checking
Interview problems and algorithms
Pattern matching in biological sequences
Cryptographic verification
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.