# Given a singly Linked List, determine if it is a Palindrome

Technology CommunityCategory: Linked ListsGiven a singly Linked List, determine if it is a Palindrome
VietMX Staff asked 1 year ago
Problem

Could you do it in O(1) time and O(1) space?

Solution: is Reversed first half == Second half?

Let’s look to an example [1, 1, 2, 1]. In the beginning, set two pointers fast and slow starting at the head.

1 -> 1 -> 2 -> 1 -> null
sf

(1) Move: fast pointer goes to the end, and slow goes to the middle.

1 -> 1 -> 2 -> 1 -> null
s          f

(2) Reverse: the right half is reversed, and slow pointer becomes the 2nd head.

1 -> 1    null <- 2 <- 1
h                      s

(3) Compare: run the two pointers head and slow together and compare.

1 -> 1    null <- 2 <- 1
h            s
Implementation
public boolean isPalindrome(ListNode head) {
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) { // odd nodes: let right half smaller
slow = slow.next;
}
slow = reverse(slow);

while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}

}