题目背景

原题：

Given a singly linked list, there will be one and only 1 duplicated pair, find it and reverse the nodes in between.

Example input: 1 -> 2 -> 3 -> 5 -> 1 -> 7 -> 8 -> null
Example output: 1 -> 5 -> 3 -> 2 -> 1 -> 7 -> 8 -> null

---

澄清问题环节

候选人提问：

1. 链表中是否可以假设只有一个重复节点对？

面试官：
是的，链表中只会有一个重复的节点对。

2. 重复节点对是否可能是相邻的，比如 1 -> 2 -> 2 这种情况？

面试官：
是的，重复的节点对可以是相邻的。

---

解题思路沟通环节

初步设计

候选人：
我打算按照以下步骤解决问题：

1. 遍历链表找到重复节点：
   我会用一个哈希表记录每个节点的值。如果在遍历过程中发现某个节点的值已经存在于哈希表中，则可以确定这是重复节点对。
2. 反转重复节点之间的部分链表：
   我会用一个辅助函数处理链表反转，通过指针操作将 start 和 end 之间的部分链表反转。
3. 连接反转后的链表：
   最后将反转后的部分与原链表正确连接。

---

数据结构与算法选择

候选人：

• 数据结构：
  使用哈希表记录已经访问过的节点值，便于快速判断是否存在重复节点。时间复杂度为 O(1)。
• 算法设计：
  反转链表的核心在于指针操作，通过记录 prev 和 next，保证链表结构不破坏。

面试官：
不错。那么能否详细描述反转部分的实现逻辑？

---

反转逻辑

候选人：
在找到重复节点对后，我们只需反转 start 和 end 之间的部分链表，操作如下：

1. 用辅助节点 dummy 连接链表头部，方便处理特殊情况。
2. 找到 start 节点的前一个节点 prev。
3. 将 start 到 end 之间的节点逐一反转，并保持剩余部分的正确连接。
4. 最后重新连接 prev、反转后的链表和 end 节点。

---

候选人模拟实现过程

示例演示

输入链表：
1 -> 2 -> 3 -> 5 -> 1 -> 7 -> 8 -> null

步骤 1：找到重复节点对

1. 初始化哈希表 visited = {}。
2. 遍历节点，依次记录值：
   • 节点值 1：加入 visited，visited = {1: Node(1)}。
   • 节点值 2：加入 visited，visited = {1: Node(1), 2: Node(2)}。
   • 节点值 3：加入 visited，visited = {1: Node(1), 2: Node(2), 3: Node(3)}。
   • 节点值 5：加入 visited，visited = {1: Node(1), 2: Node(2), 3: Node(3), 5: Node(5)}。
   • 节点值 1：已存在于 visited，确定重复节点对，start = Node(1)，end = Node(1)。

步骤 2：反转链表部分
反转链表部分 2 -> 3 -> 5：

1. prev 指向 start 的前一个节点。
2. 从 start.next 开始反转，调整每个节点的 next 指针：
   • 第一次反转：链表变为 1 -> 2 -> null。
   • 第二次反转：链表变为 1 -> 3 -> 2 -> null。
   • 第三次反转：链表变为 1 -> 5 -> 3 -> 2 -> null。

步骤 3：重新连接链表
将反转后的部分连接到原链表的后续部分，最终结果为：
1 -> 5 -> 3 -> 2 -> 1 -> 7 -> 8 -> null。

---

时间与空间复杂度分析

1. 时间复杂度：
   • 遍历链表寻找重复节点需要 O(n)。
   • 反转链表部分节点也需要 O(n)。
   • 总时间复杂度为 O(n)。
2. 空间复杂度：
   • 使用哈希表记录已访问的节点值，占用 O(n) 的空间。
   • 因此，空间复杂度为 O(n)。

---

边界条件处理

1. 重复节点相邻：
   链表为 1 -> 2 -> 2 -> 3，反转结果为 1 -> 2 -> 2 -> 3。
2. 链表只有两个节点：
   链表为 1 -> 1，反转后仍为 1 -> 1。
3. 链表长度为 1，无重复节点：
   输入链表为 1 -> null，直接返回链表。

---

面试总结

Thanks to the rigorous preparation provided by CSOAHelp's Interview Coaching and VO Support, the candidate excelled in this challenging interview. They confidently tackled each question, earning the interviewer’s praise and securing a solid opportunity for their future career. For aspiring candidates, this demonstrates the value of structured preparation and expert guidance.

经过csoahelp的面试辅助，候选人获取了良好的面试表现。如果您需要面试辅助或面试代面服务，帮助您进入梦想中的大厂，请随时联系我。

If you need more interview support or interview proxy practice, feel free to contact us. We offer comprehensive interview support services to help you successfully land a job at your dream company.