如何实现基于元组的有序链表反转Python函数？

给定元组形式的有序链表，格式为(数字, 指向下一个元组的链接)，示例：

x = (1, (3, (4, (7, (9, None)))))

需要实现反转该链表的函数，调用示例：

reverse((1, (3, (6, (8, None)))))

预期结果：

(8, (6, (3, (1, None))))

你的错误代码及问题 #

你当前的错误代码如下，运行结果为(1, (1, None))，核心问题是第一个元素重复，逻辑混乱：

def reverse(linked_list: tuple):
    last_pair = (linked_list[0], None)
    while linked_list[1]:
        new_list = (linked_list[0], last_pair)
        return new_list
        return reverse(linked_list[1])

错误原因：

• 同时混用while循环和递归，第一次进入循环就直接return new_list，递归调用永远不会执行
• 没有正确累积反转过程中的链表，仅处理第一个元素就返回，导致结果重复且不完整

正确实现方法 #

方法1：高效递归实现（推荐）

用辅助函数跟踪已构建的反转链表，每次递归将当前节点放到反转链表的头部：

def reverse(linked_list: tuple):
    def _reverse(current, reversed_list):
        if current is None:
            return reversed_list
        # 取出当前节点值，将其作为新反转链表的头部，原反转链表作为它的下一个链接
        return _reverse(current[1], (current[0], reversed_list))
    return _reverse(linked_list, None)

测试验证：调用reverse((1, (3, (6, (8, None)))))，返回(8, (6, (3, (1, None))))，完全符合预期。

方法2：迭代实现

通过循环逐个处理节点，逐步构建反转链表：

def reverse(linked_list: tuple):
    reversed_list = None
    current = linked_list
    while current is not None:
        val, next_node = current
        # 构造新的反转节点，将已反转的链表作为当前节点的下一个链接
        reversed_list = (val, reversed_list)
        current = next_node
    return reversed_list

这个方法逻辑直观，遍历一次原链表即可完成反转，时间复杂度为O(n)，空间复杂度为O(n)（因为元组不可变，每次都要创建新元组）。

补充说明 #

由于元组是不可变类型，我们无法直接修改原链表的链接关系，只能通过创建新元组的方式逐步构建反转后的链表。上述两种方法都遵循这个核心逻辑，区别仅在于遍历和构建的方式。

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