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.

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.

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.

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Duncan McArdle

Full-stack software developer from the UK, author of the Aftermath book series, full time tech-nerd.