How to know if a Linked List is Palindrome?
What is a Linked List?
It’s a data structure that visually looks like this:
What is a Palindrome?
It’s a word, phrase, numbers, etc that you can read at the same way from right/left to left/right.
level is a palindrome word
123454321 is a palindrome number
Basically what I did was go through the entire linked list with two pointers, one that runs at twice the speed of the other, this means that when the pointer that goes faster reaches the end of the array i’m sure that the other pointer is in the middle from the linked list.
We must keep in mind the number of elements that the linked list has, because the way to treat the code is slightly different if the number of elements is even or odd.
When the number of items in the linked list is odd and the fastest pointer reaches the end i know that the slowest pointer is right in the middle, but, when the number of elements is even I have to push the slower pointer one more position.
I created two main variables:
- reverse = where I capture the size of the LinkedList.
- flag = boolean way if the number of elements is even -> 0, odd -> 1
Through a loop that I will iterate one by one up to [(half the number of elements) — (flag)].
Once I enter in the loop, I’ll subtract 1 from reverse just to don’t have problems with null or try to access a position that doesn’t exist.
Valid if the element of the LinkedList in position “i” is different from the element of the LinkedList in position “reverse”
If this condition is met then immediately return “false” because it is no longer worth further evaluating.
If when exiting the loop it has not yet returned “false” that means that the LinkedList is Palindrome and I will be able to return “true”.
