Hello,

In the second edition book, the problem 8.11 Test whether a singly linked list is palindromic states that the solution has O(n) time complexity, however this seems to be wrong?

We first iterate n/2 of the list to get to the middle of the list:

while (fast && fast->next)

{

fast = fast->next->next, slow = slow->next;

}

Then we call ReverseLinkedList() starting from the middle. This entails another n/2 traversal since we start from the middle, and have to reverse the link for each node.

auto first_half_iter = L, second_half_iter = ReverseLinkedList(slow);

Finally, we perform a third traversal of n/2 elements to compare the two lists. One from the start of the array, one from the “back”.

`while (second_half_iter && first_half_iter) { if (second_half_iter->data != first_half_iter->data) { return false; } second_half_iter = second_half_iter->next; first_half_iter = first_half_iter->next; }`

So, I posit that the time complexity of the presented solution is O(1.5n) !

… Alternatively,

We could do it in O(n) time complexity and O(n/2) space if started with a slow/fast iterator, and pushed the first 50% elements into a stack. Once you reach the middle of the list, pop each element and compare to the remaining nodes.