Implement a function to check if a linked list is a palindrome

To approach this problem, we can picture a palindrome like 0 -> 1 -> 2 -> 1
– > 0. We know that, since it’s a palindrome, the list must be the same backwards and
forwards.This leads us to our first solution.

Solution #1: Reverse and Compare

Our first solution is to reverse the linked list and compare the reversed list to the original
list. If they’re the same, the lists are identical.
Note that when we compare the linked list to the reversed list, we only actually need to
compare the first half of the list. If the first half of the normal list matches the first half
of the reversed list, then the second half of the normal list must match the second half
of the reversed list.

Solution #2: Iterative Approach

We want to detect linked lists where the front half of the list is the reverse of the second
half. How would we do that? By reversing the front half of the list. A stack can accomplish
this.
We need to push the first half of the elements onto a stack. We can do this in two
different ways, depending on whether or not we know the size of the linked list.
If we know the size of the linked list, we can iterate through the first half of the elements
in a standard for loop, pushing each element onto a stack. We must be careful, of course,
to handle the case where the length of the linked list is odd.
If we don’t know the size of the linked list, we can iterate through the linked list, using
the fast runner / slow runner technique described in the beginning of the chapter. At
each step in the loop, we push the data from the slow runner onto a stack. When the
fast runner hits the end of the list, the slow runner will have reached the middle of the
linked list. By this point, the stack will have all the elements from the front of the linked
list, but in reverse order.

 

One thought on “Implement a function to check if a linked list is a palindrome

Leave a Reply

Your email address will not be published. Required fields are marked *