Forming polylines from a list of individual lines
Loop over all invidivual lines. If a point of the line is the same as one of the polylines head or tail, extend the polyline
  


(My emphasis). How are you doing that test? To take $\Theta(n^2)$ time, I think you must be testing each point by linear scan in $\Theta(n)$. Use a decent hashmap instead and it will take $\Theta(1)$ on average.