Check whether a singly linked list is a palindrome

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}