Oracle OCI：手写单链表并原地反转

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版为单向链表，提供 append、find、removeFirst、reverse、values；这些方法名和删除行为不是题目公开接口。
• reverse 原地修改 next 并更新 head，不新建节点；空链和单节点均允许。

解题路线

1. Node 只存 value 与 next，列表保存 head。append 沿链走到尾部再接新节点；若频繁 append，可另存 tail 将其优化到 O(1)。
2. removeFirst 用 previous/current 双指针，命中头节点时单独更新 head；未命中返回 false。
3. reverse 同时维护 previous、current、following：先保存 current.next，再反指向 previous，最后推进。每轮已处理前缀被完整反转，未处理后缀仍从 current 可达。
4. 循环结束 previous 是新头；千万不能在保存 following 前改 next，否则后续节点丢失。

手动走一遍

1→2→3：第一轮得到 1→None、current=2；第二轮得 2→1、current=3；第三轮得 3→2→1，head 更新为 3。空链反转仍为空。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Training singly linked list with append, find, remove and in-place reverse."""


class Node:
    def __init__(self, value, next_node: "Node | None" = None):
        self.value = value
        self.next = next_node


class SinglyLinkedList:
    def __init__(self):
        self.head: Node | None = None

    def append(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = node

    def find(self, value) -> bool:
        current = self.head
        while current is not None:
            if current.value == value:
                return True
            current = current.next
        return False

    def remove_first(self, value) -> bool:
        previous = None
        current = self.head
        while current is not None:
            if current.value == value:
                if previous is None:
                    self.head = current.next
                else:
                    previous.next = current.next
                return True
            previous, current = current, current.next
        return False

    def reverse(self) -> None:
        previous = None
        current = self.head
        while current is not None:
            following = current.next
            current.next = previous
            previous = current
            current = following
        self.head = previous

    def values(self) -> list:
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result

复杂度

append 未存 tail 为 O(N)，find/removeFirst 为 O(N)，reverse 为 O(N) 时间、O(1) 额外空间；values 输出 O(N)。训练代码选简洁接口，题目未要求 append 的目标复杂度。

易错点与追问

容易失分的边界

• 反转时先改 next 再保存后继，失去后半链。
• 删除首节点时只改局部变量，不更新 list.head。
• 创建新链表再逆序复制却声称是原地反转。

继续深挖

• 若保存 tail，反转完成后 tail 应指向哪个节点？
• 若要检测并处理环，reverse 前需怎样防止无限循环？