Given an array composed of pairs, like this:

((3,5),(1,5),(3,2),(1,4))

Each element in the array (call it pair) means that pair(0) and pair(1) are adjacent in the original array. Note, they can come in either order. For instance, for the sample array above, the original array would be:

4,1,5,3,2 (or the reversed version of this)

**How can I do this quickly? I tried doing this as follows, which works, but it’s too slow:**

Create a hashmap that maps adjacent elements. Map = {3: (5,2), 1: (5,4), 5: (1,3), 4: (1), 2:(3)}. My algorithm would then start with one of the keys that only has a corresponding value length of 1 (in this case either 4 or 2), and then add to an output array, and go through the hashmap. I.e. First I would add 4 to my output, and then go from key of 4 (with a corresponding value of 1), to the key of 1, with corresponding values of 5 and 4. I’d ignore 4 (since it’s already in output), and add 5, then go to the key of 5, and so on and so forth. This is too slow! Is there a better algorithm?