Palindrome Linked List
EasyPrompt
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Input: head = [1,2,2,1]
Output: trueExample 2:
Input: head = [1,2]
Output: false
Constraints:
- The number of nodes in the list is in the range
[1, 105]. 0 <= Node.val <= 9
Follow up: Could you do it in
O(n) time and O(1) space?Approaches
3 approaches with complexity analysis and trade-offs.
Convert the linked list to an array and use two pointers to check if it's a palindrome.
Algorithm
- Create an ArrayList to store the values
- Traverse the linked list and add all values to the ArrayList
- Use two pointers (left and right) starting from the beginning and end of the ArrayList
- Compare values at left and right pointers
- Move left pointer forward and right pointer backward
- If any values don't match, return false
- If all values match, return true
Walkthrough
This approach involves converting the linked list to an array first, then using two pointers (one from start and one from end) to check if the values match. While this is the most straightforward solution, it requires extra space to store the array.
class Solution { public boolean isPalindrome(ListNode head) { List<Integer> values = new ArrayList<>(); // Convert linked list to array ListNode current = head; while (current != null) { values.add(current.val); current = current.next; } // Use two pointers to check palindrome int left = 0; int right = values.size() - 1; while (left < right) { if (!values.get(left).equals(values.get(right))) { return false; } left++; right--; } return true; }}```Complexity
Time
O(n) where n is the number of nodes in the linked list
Space
O(n) to store the array of values
Trade-offs
Pros
Easy to implement and understand
Good for interviews when asked to provide a quick solution
Can handle null and single node cases easily
Cons
Uses extra space to store the array
Not the most efficient solution in terms of space complexity
Requires two passes through the data
Use a stack to store the first half of the linked list and then compare with the second half.
Algorithm
- Initialize a stack and two pointers (slow and fast)
- Move fast pointer twice as fast as slow pointer
- Push elements onto stack until slow reaches middle
- Skip middle element if list length is odd
- Compare remaining elements with stack elements
- Return false if any elements don't match
- Return true if all elements match
Walkthrough
This approach uses a stack to store the first half of the linked list. First, find the middle of the linked list using slow and fast pointers. Push elements onto the stack until the middle is reached. Then compare the remaining elements with the top of the stack.
class Solution { public boolean isPalindrome(ListNode head) { Stack<Integer> stack = new Stack<>(); ListNode slow = head; ListNode fast = head; // Push first half elements onto stack while (fast != null && fast.next != null) { stack.push(slow.val); slow = slow.next; fast = fast.next.next; } // If odd length, skip middle element if (fast != null) { slow = slow.next; } // Compare second half with stack while (slow != null) { if (stack.isEmpty() || stack.pop() != slow.val) { return false; } slow = slow.next; } return true; }}```Complexity
Time
O(n) where n is the number of nodes in the linked list
Space
O(n/2) to store half of the elements in the stack
Trade-offs
Pros
More space-efficient than converting to array
Only requires one pass through the linked list
Handles both odd and even length lists
Cons
Still requires extra space for the stack
More complex implementation than array approach
Not the most space-efficient solution possible
Find the middle of the linked list, reverse the second half, and compare with the first half.
Algorithm
- Find the middle of the linked list using slow and fast pointers
- Reverse the second half of the linked list in-place
- Compare the first half with the reversed second half
- Return false if any values don't match
- Return true if all values match
Walkthrough
This is the most efficient approach that achieves O(1) space complexity. It works by first finding the middle of the linked list using slow and fast pointers, then reversing the second half of the list in-place, and finally comparing the first half with the reversed second half.
class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; // Find middle using slow/fast pointers ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } // Reverse the second half ListNode secondHalf = reverseList(slow.next); // Compare first half with reversed second half ListNode firstHalf = head; while (secondHalf != null) { if (firstHalf.val != secondHalf.val) { return false; } firstHalf = firstHalf.next; secondHalf = secondHalf.next; } return true; } private ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; }}```Complexity
Time
O(n) where n is the number of nodes in the linked list
Space
O(1) as it only uses a constant amount of extra space
Trade-offs
Pros
Optimal space complexity O(1)
Handles all cases efficiently
Meets the follow-up challenge requirement
Only requires one pass through the list
Cons
Modifies the original linked list structure
More complex implementation
Need to restore the original list if modification is not allowed
Solutions
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public bool IsPalindrome ( ListNode head ) { ListNode slow = head ; ListNode fast = head . next ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; } ListNode cur = slow . next ; slow . next = null ; ListNode pre = null ; while ( cur != null ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } while ( pre != null ) { if ( pre . val != head . val ) { return false ; } pre = pre . next ; head = head . next ; } return true ; } }/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome ( ListNode head ) { ListNode slow = head ; ListNode fast = head . next ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; } ListNode cur = slow . next ; slow . next = null ; ListNode pre = null ; while ( cur != null ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } while ( pre != null ) { if ( pre . val != head . val ) { return false ; } pre = pre . next ; head = head . next ; } return true ; } }/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {boolean} */ var isPalindrome = function (head) { let slow = head; let fast = head.next; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } let cur = slow.next; slow.next = null; let pre = null; while (cur) { let t = cur.next; cur.next = pre; pre = cur; cur = t; } while (pre) { if (pre.val !== head.val) { return false; } pre = pre.next; head = head.next; } return true; };/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: bool isPalindrome ( ListNode * head ) { ListNode * slow = head ; ListNode * fast = head -> next ; while ( fast && fast -> next ) { slow = slow -> next ; fast = fast -> next -> next ; } ListNode * pre = nullptr ; ListNode * cur = slow -> next ; while ( cur ) { ListNode * t = cur -> next ; cur -> next = pre ; pre = cur ; cur = t ; } while ( pre ) { if ( pre -> val != head -> val ) return false ; pre = pre -> next ; head = head -> next ; } return true ; } };# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def isPalindrome ( self , head : Optional [ ListNode ]) -> bool : slow , fast = head , head . next while fast and fast . next : slow , fast = slow . next , fast . next . next pre , cur = None , slow . next while cur : t = cur . next cur . next = pre pre , cur = cur , t while pre : if pre . val != head . val : return False pre , head = pre . next , head . next return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.