题目描述
思路解析
一句话答案：LeetCode 1743 从相邻元素对还原数组：把打乱的相邻对当无向边建图，链两端的度恰好是 1，从端点带着 prev 沿边走一遍就还原出整个顺序，时间 O(n)。
adjacentPairs 只给了相邻关系，要还原成什么
给你一个二维数组 adjacentPairs，长度 n 减 1，每一项 [u, v] 只说明 u 和 v 在原数组 nums 里挨着，但谁左谁右不定、各对也乱序。nums 里的数互不相同、可能为负、绝对值到十万，要把这些散乱的相邻关系拼回 nums。题面 adjacentPairs = [[2,1],[3,4],[3,2]] 还原成 [1,2,3,4]；带负数的例子答案 [-3,1,4,-2]，倒着写也对。
把相邻对排序首尾接起来，为什么接不成链
顺手容易想到把相邻对排序再首尾相接拼成链。可 [u, v] 谁前谁后不定、各对排列也乱，排序无从下手，拼接也不知该接哪端——[2,1] 摆成 …2,1… 还是 …1,2…？排序拼不出唯一顺序。真正稳的信息不是先后，而是「谁和谁相邻」这层关系，得换种结构装它。
相邻对看成边之后，链的两头藏着什么信号
把每一对 [u, v] 看成一条连 u 和 v 的无向边，n 个数就是 n 个点、n 减 1 条边的图。原数组本是一条线：最左的数只有右邻居、最右的只有左邻居，首尾各只连一条边，度，也就是邻居个数，恰好是 1；中间每个数左右各一个邻居，度是 2。两端于是有了精准标记——全图里度为 1 的，只会是链的两端点。
认准度为 1 的端点，带着 prev 把链走通
实现上先用哈希表 g 建邻接表：遍历每对 a、b，往 g[a] 塞 b、g[b] 塞 a，互相登记。建完扫一遍挑出只有一个邻居的键当端点，取较小的作起点 start。再从 start 沿边走：prev 记上一步、cur 记当前点，每到一处先把 cur 填进答案，再选不等于 prev 的那个邻居当下一站 nxt。中间点两个邻居总有一个是 prev，跳过它才不原地折返；走到另一端点时下一站为空，链到头。
顺着 [[2,1],[3,4],[3,2]] 从头建图走一遍
就用题面 adjacentPairs = [[2,1],[3,4],[3,2]]。建图：[2,1] 让 g[2]=[1]、g[1]=[2]；[3,4] 让 g[3]=[4]、g[4]=[3]；[3,2] 再往 g[3] 添 2、g[2] 添 3。最终 g[1]=[2]、g[2]=[1,3]、g[3]=[4,2]、g[4]=[3]。度为 1 的是 1 和 4，取较小的 1 当起点。开走：cur=1 填答案，邻居只有 2，去 2；到 2，邻居 [1,3] 里 1 是 prev 跳过，去 3；到 3，邻居 [4,2] 里 2 是 prev 跳过，去 4；到 4，邻居只剩 prev，下一站为空。答案 [1,2,3,4]，对上题面。
从中间点起步会乱套，负数和 n=2 要不要另写
复杂度很干净：建图、扫端点、沿链各点访问一次，没排序没嵌套循环，时间 O(n)；邻接表条目约为边数两倍，空间 O(n)。几处易走偏：从中间点起步会乱套，它两向都通、一次定不下序，得认准度为 1 的端点再出发；走中间点忘带 prev，会朝来路折回、两点间反复横跳；还有别拿数值直接当下标，值到正负十万会越界。边界上，n 等于 2 时两点都是端点、随便起步都行，含负数照常建图，多解正倒都对。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢三件事:相邻对就是边、度为 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;所谓建图就是那张值到邻居的哈希表。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]: g = defaultdict(list) for a, b in adjacentPairs: g[a].append(b) g[b].append(a) start = min(x for x, ns in g.items() if len(ns) == 1) ans, prev, cur = [], None, start while cur is not None: ans.append(cur) nxt = None for v in g[cur]: if v != prev: nxt = v break prev, cur = cur, nxt return ans复杂度
- 时间：O(n)，建图遍历 n 减 1 个相邻对是 O(n);扫一遍找度为 1 的端点是 O(n);沿链走每个点恰好访问一次也是 O(n),合起来线性
- 空间：O(n)，邻接表要为每个值存它的邻居,总条目数是边数的两倍即 2 乘 n 减 1,峰值与 n 同阶;输出数组也是 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么两个端点的度数一定是 1,中间元素一定是 2?
追问能不能不真的建图?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
地图中的最高点
LeetCode 1765 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题