The problem specifically says “Your algorithm should use constant space and the input LinkedList should be in the original form once the algorithm is finished.”
The solution seems to lose the head.
We have to preserve the head .
1 Like
I noticed the same. Head is lost. All we have is the middle-head of the list. If the head is lost, we can’t check if the list has really been kept unchanged.
Actually, no. When you reach the middle and reverse the second half, the middle node is being referenced from two sides, front and reverse, while the node itself is pointing to null. When you reverse it back, you make the middle node being referenced only from the front, and its null referencing link is reused to refer to the old tail of the second half, returning the list to it’s original shape.
N
^
|
1->2->3->2->1 ======> 1->2->3<-2<-1 ======> 1->2->3->2->1
1 Like
Very nicely explained, I could not visualize how it was happening. thanks