Errata: 8.11 Palindromic list - O time complexity

#1

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.

0 Likes