Given the head of a singly linked list, return true if it is a palindrome.
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Given the List Node class.
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
What is palindrome?
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar. There are also numeric palindromes, including date/time stamps using short digits 11/11/11 11:11 and long digits 02/02/2020. Sentence-length palindromes ignore capitalization, punctuation, and word boundaries.Wikipedia
Solution 1
Traverse the whole linked list and store the values into a string variable; and then check whether or not the string is a palindrome.
/**
* @param {string} st
* @return {boolean}
* @time complexity: O(n)
* @space complexity: O(n)
*/
const isValidPalindrome = str => {
let i = 0;
let j = str.length - 1;
while (i < j) {
if (str[i] !== str[j]) {
return false;
}
i++;
j--;
}
return true;
};
/**
* @param {ListNode} head
* @return {boolean}
* @time complexity: O(n)
* @space complexity: O(n)
*/
const isPalindrome = head => {
let str = '';
while (head) {
str += head.val;
head = head.next;
}
return isValidPalindrome(str);
};
Solution 2
We can also write a Rrecursive function to check the values whether they are palindrome.
/**
* @param {ListNode} head
* @return {boolean}
* @time complexity: O(n)
* @space complexity: O(n)
*/
const isPalindrome2 = head => {
const reverseCheck = node => {
if (node !== null) {
if (!reverseCheck(node.next)) {
return false;
}
if (node.val !== head.val) {
return false;
}
head = head.next;
}
return true;
};
return reverseCheck(head);
};
Test Case
const assert = require('chai').assert;
const createLinkedList = arr => {
const dummy = new ListNode();
let curr = dummy;
for (const ele of arr) {
curr.next = new ListNode(ele);
curr = curr.next;
}
return dummy.next;
};
describe('Palindrome Linked List', () => {
describe('Solution 1', () => {
it('should return true', () => {
const input = createLinkedList([1, 2, 2, 1]);
const result = isPalindrome(input);
const expected = true;
assert.strictEqual(result, expected);
});
it('should return false', () => {
const input = createLinkedList([1, 2]);
const result = isPalindrome(input);
const expected = false;
assert.strictEqual(result, expected);
});
});
describe('Solution 2', () => {
it('should return true', () => {
const input = createLinkedList([1, 2, 2, 1]);
const result = isPalindrome2(input);
const expected = true;
assert.strictEqual(result, expected);
});
it('should return false', () => {
const input = createLinkedList([1, 2]);
const result = isPalindrome2(input);
const expected = false;
assert.strictEqual(result, expected);
});
});
});
Palindrome Linked List
Solution 1
✓ should return true
✓ should return false
Solution 2
✓ should return true
✓ should return false
4 passing (14ms)
