Given the head of a singly linked list, return true if it is a palindrome
(reads the same forward and backward), or false otherwise.
Try to solve it in O(n) time and O(1) space.
Input: head = [1, 2, 2, 1]
Output: true
Input: head = [1, 2]
Output: false
Input: head = [1, 2, 3, 2, 1]
Output: true
The O(1) space approach uses three steps: find the middle of the list, reverse the second half in-place,
then compare the two halves node by node.
- Step 1 - Find the middle: Use slow and fast pointers. When fast reaches the end, slow is at the middle.
- Step 2 - Reverse second half: Reverse the sublist starting from slow.next.
- Step 3 - Compare: Compare nodes from the head and from the reversed second-half head simultaneously. If all values match, it is a palindrome.
- Optionally restore the list by reversing the second half again.
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class PalindromeLinkedList {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// Step 1: Find middle using slow/fast pointers
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half
ListNode secondHalf = reverse(slow);
// Step 3: Compare first and second halves
ListNode p1 = head;
ListNode p2 = secondHalf;
boolean palindrome = true;
while (p2 != null) {
if (p1.val != p2.val) {
palindrome = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
// Restore list (optional but good practice)
reverse(secondHalf);
return palindrome;
}
private ListNode reverse(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 Analysis:
Time complexity: O(n) — finding the middle is O(n/2), reversing is O(n/2), comparing is O(n/2).
Space complexity: O(1) since we reverse in-place and use only a constant number of pointers.