1
class Solution {
2
  public int[] restoreArray(int[][] adjacentPairs) {
3
    // Build an adjacency list graph.
4
    Map<Integer, Queue<Integer>> iToPairs = new HashMap<>();
5
    for (int[] pair : adjacentPairs) {
6
      iToPairs.computeIfAbsent(pair[0], k -> new ArrayDeque<>()).add(pair[1]);
7
      iToPairs.computeIfAbsent(pair[1], k -> new ArrayDeque<>()).add(pair[0]);
8
    }
9

10
    // Find an item that has only one neighbour.
11
    int start = -1;
12
    for (int i : iToPairs.keySet()) {
13
      if (iToPairs.get(i).size() == 1) {
14
        start = i;
15
        break;
16
      }
17
    }
18

19
    // Traverse the graph in a linked-list fashion.
20
    int n = iToPairs.size();
21
    int writeIdx = 0;
22
    int[] restored = new int[n];
23
    restored[writeIdx++] = start;
24
    while (writeIdx < n) {
25
      int next = iToPairs.get(start).remove();
26
      iToPairs.remove(start);
27
      iToPairs.get(next).remove(start); // Remove the loop back to the current start.
28
      restored[writeIdx++] = next;
29
      start = next;
30
    }
31

32
    return restored;
33
  }
34
}