如何按首尾值匹配规则重新排序元组列表？

你需要将元组列表按「后一个元组起始值等于前一个元组结尾值」的规则排序，且允许反转元组来满足匹配条件。原代码的问题在于：

1. 仅构建了元组正向的邻接关系，完全没考虑元组可反转的情况
2. 使用的DFS遍历仅记录节点访问顺序，未处理边的唯一性（可能重复使用元组）
3. 节点序列转元组的逻辑简单粗暴，无法对应原元组或其反转形式

这个问题本质是寻找欧拉路径：把每个元组看作可双向使用的边，数值看作节点，我们需要找到一条路径，每条边仅使用一次，且相邻边首尾相连。具体步骤：

1. 构建双向图：每个元组同时添加正向（a→b）和反向（b→a）的边，并标记边是否已使用
2. 确定起始节点：统计每个节点的度数，若存在两个奇数度节点，选其中一个作为起点；若全为偶数度，任选一个节点即可
3. 用Hierholzer算法遍历图，生成节点路径，再转换为符合要求的元组序列

def find_chain(tuples_list):
    # 构建双向图，记录边的索引和是否反转
    graph = {}
    edge_used = [False] * len(tuples_list)
    
    for idx, (a, b) in enumerate(tuples_list):
        # 添加正向边
        if a not in graph:
            graph[a] = []
        graph[a].append((b, idx, False))
        # 添加反向边
        if b not in graph:
            graph[b] = []
        graph[b].append((a, idx, True))
    
    # 统计节点度数，确定起始节点
    degree = {}
    for a, b in tuples_list:
        degree[a] = degree.get(a, 0) + 1
        degree[b] = degree.get(b, 0) + 1
    
    start = None
    for node in degree:
        if degree[node] % 2 != 0:
            start = node
            break
    # 无奇数度节点时，任选一个存在的节点
    if start is None:
        start = next(iter(graph.keys()))
    
    # Hierholzer算法寻找欧拉路径
    stack = [start]
    path = []
    
    while stack:
        current = stack[-1]
        found_unused_edge = False
        # 遍历当前节点的所有边，找未使用的
        for i in range(len(graph.get(current, []))):
            neighbor, edge_idx, is_reversed = graph[current][i]
            if not edge_used[edge_idx]:
                edge_used[edge_idx] = True
                stack.append(neighbor)
                # 删除已处理的边，避免重复遍历
                del graph[current][i]
                found_unused_edge = True
                break
        if not found_unused_edge:
            # 回溯，将节点加入路径
            path.append(stack.pop())
    
    # 反转路径得到正确顺序，再转换为元组序列
    path = path[::-1]
    return [(path[i], path[i+1]) for i in range(len(path)-1)]

# 测试
tuples_list = [(1, 3), (-6, 3), (1, 7)]
print(find_chain(tuples_list))  # 输出示例：[(7, 1), (1, 3), (3, -6)]

• 该算法会生成所有符合规则的序列之一，你的预期结果是其中一种合法输出
• 算法保证每个元组仅被使用一次（正向或反转）
• 适用于任意规模的元组列表，只要存在合法的链式序列

内容的提问来源于stack exchange，提问作者MadVillain_