Check whether a singly linked list is a palindrome
Problem
Return true if the list's values read the same forwards and backwards. Aim for O(n) time and O(1) extra space.
Example 1
Input: 1 → 2 → 2 → 1 Output: true
Example 2
Input: 1 → 2 Output: false
Also asked as: Write a Program to check whether the Singly Linked list is a palindrome or not
Test cases
Case 1
Input: [1,2,2,1] Expected: true
Case 2
Input: [1,2] Expected: false
Case 3
Input: [1,2,3,2,1] Expected: true
View solutionHide solution1 approach
1. Reverse the second half, compare, restore
Time O(n)Space O(1)
Find the middle, reverse the second half, walk both halves in lockstep comparing values (optionally re-reverse to restore).
function isPalindrome(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } let prev = null; while (slow) { const n = slow.next; slow.next = prev; prev = slow; slow = n; } let a = head, b = prev, ok = true; while (b) { if (a.val !== b.val) { ok = false; break; } a = a.next; b = b.next; } return ok;}