Checking if a Linked List is a Palindrome

Algorithm:

1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the second half again and attaching it back to the first half.

Time complexity: O(n)
Space complexity: O(1)