Find the origin and the destination of a trip from a serie of tickets
Using a hash table, record for each city mentioned how many times it was mentioned as a source and how many as destination. The source of the trip is the city that has appeared as a source an odd number of times, and similarly for the destination of the trip. That's linear time and space (with high probability).

Also, as Jan comments, the statistic that should be odd is the total number of times that the city has appeared. If a city appeared an odd number of times, then it is the source if it appeared as a source more than as a destination, and vice versa for destination.