Back to DSA
Palindrome Linked List
easyDetermine whether a singly linked list forms a palindrome — that is, the sequence of values reads the same from front to back as from back to front. Return true if it does, false otherwise.
Examples
Example 1:
Input:
head = [3,7,7,3]Output:
true Example 2:
Input:
head = [1,5]Output:
falseHints
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null;
while (slow != null) {
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
ListNode left = head, right = prev;
while (right != null) {
if (left.val != right.val) return false;
left = left.next;
right = right.next;
}
return true;
}
}Time complexity
O(n)Space complexity
O(1)