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
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 ; } }Video 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.