Restore the Array From Adjacent Pairs

Given adjacent pairs of a hidden array, reconstruct the original array. Pattern focus: Graph Degree Analysis. The endpoints have degree 1, and the rest of the nodes have degree 2.

Input Format

adjacentPairs = list of adjacent pairs from the original array

Output Format

the reconstructed original array

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • adjacentPairs must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

adjacentPairs = [[2,1],[3,4],[3,2]]

Output:

[1,2,3,4]

Explanation:

The endpoints are 1 and 4.

Example 2:

Input:

adjacentPairs = [[4,-2],[1,4],[-3,1]]

Output:

[-2,4,1,-3]

Explanation:

Degree-1 nodes determine the endpoints.

Loading...
Restore the Array From Adjacent Pairs