Linkedlist Palindrome Algorithm

Problem: Check if a (extra-large) singly linked list of charcters is a palindrome or not.
Solution1:
The brute force algorithm is to revese the linked list and check if the original and reversed linked lists are equal.
Time Complexity: O(n)
Space Compexity: Not good, as it requires an extra linked list.
Solution 2:
1. Find the middle node of the list: This can be done by looping through the list, using two pointers and incrementing the second pointer by 1 only when the first pointer is increamented by two steps. The second pointer would give the middle node of the list, when the first pointer reaches the end of the linked list.
2. Reverse the first half of the linked list.
3. Check if the first half and the second half of the list are equal.
Time Complexity: O(n)
Space Complexity: Better than the first, as we are using only a single linked ist.

If there is a better algorithm, please add to the comments.