Problem: Given a singly linked list, determine if it is a palindrome.
Method 1: Create an array of values
The structure of a linked list doesn't provide access to the total size of the list. To get around this we can iterate over the list and push the node values on to an array. At that point we have access to the array's length and can use a single pointer i to compare values opposite to eachother in the array.
var isPalindrome = function(head) {
let values = []
// push all node values into an array
while (head !== null) {
values.push(head.val)
head = head.next
}
// iterate over array and compare values
for (let i = 0; i < values.length >> 1; i++) {
// (values.length - i - 1) is our virtual pointer
if (values[i] !== values[values.length - i - 1]) return false
}
return true
};
The time and space complexity of this method are O(n)
Method 2: Reverse the Second Half in Place
We can use a fast and slow pointer to get to the center and the end of the list, respectively. Once we are able to determine the center, we use the slow pointer to re-link the second half of the list in reverse. I like to conceptualize this method as taking a snake and turning its tail into a head, resulting in a two headed snake with a tail (ListNode.next = null) in the middle.
var isPalindrome = function(head) {
if (head === null || head.next == null) return true
let slow = head
let fast = head
while (fast !== null && fast.next !== null) {
fast = fast.next.next
slow = slow.next
}
// if list length is odd, move slow over one to start
// the second half of the list
if (fast) {
slow = slow.next
}
// reverse the second half of the list
slow = reverse(slow)
fast = head
// check for palindromicity
while (slow) {
if (slow.val !== fast.val) {
return false
}
slow = slow.next
fast = fast.next
}
return true
}
function reverse(head) {
let prev = null
let next;
while (head) {
next = head.next
head.next = prev
prev = head
head = next
}
return prev
}
The time complexity is O(n) and space complexity is O(1) as we are not creating any extra arrays.
Top comments (1)
This code is difficult to understand. Variable names, especially when goes like this: fast = head, and expressions like reverse(slow).
I think it would better to go to the end saving the prev node to prev property and when you achieve the end, you can just compare head and last.prev and go ahead until node links are the same. What do you think about it?