Leetcode 234: Palindrome Linkedlist

I am looking at a solution for 234. Palindrome Linked List: Given the head of a singly linked list, return true if it is a palindrome. This is a correct solution: class Solution:

Solution 1:

There is an error in your modified version Your logic is correct but when your reverse function is defined to reverse the list from the parameter pass so, f_p would be pointing to the last element, not the middle element. The leetcode version solution compares value from starting to values from the reversed second half.

Solution 2:

The idea according to this YouTube video ... is that we take the first half of the list, reverse it, and compare.

This is a misunderstanding. It actually reverses the second half of the list. The correct code reverses the list that starts at s_p (slow pointer). This is not the first half of the list, but the second half. The first half would start exactly where the whole lists starts: at head. The loop that lets the s_p and f_p references walk along the list will end when f_p is near the end of the list, and s_p is therefore half-way the list.

Your code reverses the list that starts at f_p (fast pointer), but that pointer is referring to the last or one-but-last node in your list (look at the while condition), so if anything, it only reverses the final two nodes of the list! This is obviously not correct.