LeetCode problem #234: Palindrome Linked List (JavaScript)

In this LeetCode problem, we’re given a Linked List, and asked to determine whether or not it (or rather, its values) represents a palindrome.

Revision point 1: A linked list is a data structure that consists of two properties; next which points to the next node in the list, and val which tells you the current node’s value.

Revision point 2: A palindrome is something that is the same when reversed. For example, “dad” is a palindrome, as is “12321”, but “test” is not, and nor is “123”.

What we’re being asked here then, is to get the values from a Linked List, reverse them, and see if they remain the same. For example, in the Linked List 1 -> 2 -> 1, if we pull out the values to make the array [1, 2, 1], and then reverse it, we can see it remains the same and is thus a palindrome.

Solution #1: Array of values

Much like in the above explanation, our approach here will be first to loop through the values of the supplied Linked List, adding them to an array, and then to determine whether or not that array represents a palindrome.

This approach is fast, but it isn’t great on memory, as we’re creating a new block of data that is proportionate to the original Linked List.

Solution #2: Recursive

In this solution, we first make a recursive call that traverses its way through the supplied Linked List. Then, as each call begins to finish (starting with the final node), we compare it with the original head. In other words, we compare the first node with the last, and then move both inward.

It’s a clever approach and comes without the memory intensity of the former one. It’s also readable and very compact.

Solution #3: Reversing the second-half

Another popular approach is to reverse the Linked List from the middle point onwards, and then compare the start and end nodes, moving inwards each time. This can be done using either a recursive or iterative approach, but here we’ve done it iteratively.