从相邻元素对还原数组

记牢三件事:相邻对就是边、度为 1 的是端点、走链时跳过来时的邻居。下面一帧帧套它。

建图 · 5 个点还没有边：先把出现过的 5 个数摆成 5 个点:15、40、27、33、58。此刻它们之间一条边都没有,右边的邻接表也是空的。接下来把 adjacentPairs 里的每一对,都连成一条无向边。

看第 0 对 · [27, 40]：看第 0 对相邻元素 [27, 40],它说明 27 和 40 在原数组里紧挨着。先把这两个点点亮,准备在它们之间连一条无向边。

连边 · 27 — 40：连上 27 和 40 这条边。因为是无向的,两边都要记:27 的邻居里加上 40、40 的邻居里加上 27。看右边面板,27 现在的度是 1、40 的度是 1。继续下一对。

看第 1 对 · [33, 58]：看第 1 对相邻元素 [33, 58],它说明 33 和 58 在原数组里紧挨着。先把这两个点点亮,准备在它们之间连一条无向边。

连边 · 33 — 58：连上 33 和 58 这条边。因为是无向的,两边都要记:33 的邻居里加上 58、58 的邻居里加上 33。看右边面板,33 现在的度是 1、58 的度是 1。继续下一对。

看第 2 对 · [15, 40]：看第 2 对相邻元素 [15, 40],它说明 15 和 40 在原数组里紧挨着。先把这两个点点亮,准备在它们之间连一条无向边。

连边 · 15 — 40：连上 15 和 40 这条边。因为是无向的,两边都要记:15 的邻居里加上 40、40 的邻居里加上 15。看右边面板,15 现在的度是 1、40 的度是 2。继续下一对。

看第 3 对 · [27, 33]：看第 3 对相邻元素 [27, 33],它说明 27 和 33 在原数组里紧挨着。先把这两个点点亮,准备在它们之间连一条无向边。

连边 · 27 — 33：连上 27 和 33 这条边。因为是无向的,两边都要记:27 的邻居里加上 33、33 的邻居里加上 27。看右边面板,27 现在的度是 2、33 的度是 2。四条边全连完,图就建好了。

找端点 · 度为 1 的点：图建好了,扫一遍每个点的度。度为 2 的 40、27、33 都是被夹在中间的元素,而度为 1 的只有 15 和 58 这两个点,它们各自只有一个邻居,正是这条链的两个端头。

定起点 · 从较小端点 15 出发：从哪一端起步都能得到合法答案。参考解统一从较小的那个端点出发,也就是 15。把它标成起点,接下来沿着边一个点一个点往前走,同时把走过的值填进还原数组。

沿链走 · 当前 15：从起点 15 看起。它是端点,邻居只有 40 一个,方向没有悬念,下一步就走向 40。

把起点 15 填进还原数组的第 0 位。目前 nums 是 [15]。

沿链走 · 当前 40：走到 40。它有两个邻居:27 和 15。其中 15 是刚才来的那个,跳过它;另一个 27 就是要去的下一站,把这条边点亮。

把 40 接到还原数组第 1 位。灰色的问号是还没填的位置,继续往后走。

沿链走 · 当前 27：走到 27。它有两个邻居:40 和 33。其中 40 是刚才来的那个,跳过它;另一个 33 就是要去的下一站,把这条边点亮。

把 27 接到还原数组第 2 位。灰色的问号是还没填的位置,继续往后走。

沿链走 · 当前 33：走到 33。它有两个邻居:58 和 27。其中 27 是刚才来的那个,跳过它;另一个 58 就是要去的下一站,把这条边点亮。

把 33 接到还原数组第 3 位。灰色的问号是还没填的位置,继续往后走。

沿链走 · 当前 58：走到 58。它是另一个端点,唯一的邻居 33 正是上一步来的地方,没有新的可走,链到此为止,全部还原完成。

把 58 接到还原数组第 4 位。它是链尾,数组填满了。

整条链走完,还原数组是 [15, 40, 27, 33, 58]。你可以核对一下:相邻的 15-40、40-27、27-33、33-58 恰好就是题目给的四对,一个不多一个不少,还原正确。反着写成 [58, 33, 27, 40, 15] 也是合法答案。

边界先想清:n 等于 2 时两点都是端点;有负数照样建图;多解时正反皆可。

两个高频追问:线性排列决定了端点度 1、中间度 2;所谓建图就是那张值到邻居的哈希表。