我被问到这个问题是为了通过有效地使用线程来反转一个拥有 700 万个节点的单链表。如果有这么多节点，使用递归看起来不可行，所以我选择了分而治之，在每个线程中给定一个链表块，只需通过存储引用来使节点指针指向前一个节点，就可以反转它当前，未来和过去的节点，然后将其与其他线程的反向块一起添加。但是面试官坚持认为链表的大小是不知道的，不用找到大小就可以做到。好吧，我想不通，你会怎么做呢？
问问题
657 次
1 回答
1
我喜欢实施“自上而下”的此类问题：
- 假设您已经有一个实现 Runnable 或扩展 Thread 的类，您可以从中创建实例并运行，每个实例接收两个参数：指向列表中节点的指针和要反转的节点数
- 您
main遍历所有 700 万个节点并“标记”线程的起点，假设我们有 7 个线程，标记点将是：1、1,000,000、2,000,000,... 将标记节点保存在数组或任何数据结构中你喜欢 - 完成“标记起点后，创建线程并为每个线程指定起点和计数器 1,000,000
- 在所有线程完成后，“粘合”每个标记点以指向前一个线程的最后一个节点（应保存在另一个“静态”有序数据结构中）。
现在我们有了一个计划——剩下要做的就是实现一个（相当简单的）算法，给定数字 N 和一个节点 x，它将反转单链表中的下 N 个节点（包括 x）:)
于 2013-08-10T19:03:40.700 回答