Java:块中的LinkedList反转

Question

如果您被提供链表的头部,并被要求反转每个k序列的节点,那么如何在Java中完成？例如,a->b->c->d->e->f->g->hk = 3即可c->b->a->f->e->d->h->g->f

任何一般帮助甚至伪代码将不胜感激!谢谢!

Answer 1

如果k预期相当小，我会选择最简单的事情：根本忽略它是一个链表的事实，并将每个子序列视为要反转的数组类型的东西。

因此，如果您的链表的节点类是 a Node<T>，请创建一个Node<?>[]大小为 的k。对于每个段，加载k Nodes到数组列表中，然后通过一个简单的for循环反转它们的元素。在伪代码中：

// reverse the elements within the k nodes
for i from 0 to k/2:
    nodeI = segment[i]
    nodeE = segment[segment.length-i-1]
    tmp = nodeI.elem
    nodeI.elem = nodeE.elem
    nodeE.elem = tmp

优点：非常简单，O(N) 性能，利用易于识别的反转算法。

缺点：需要一个k- 大小的数组（只需一次，因为您可以在每个段中重复使用它）

另请注意，这意味着Node列表中的每个对象都不会移动，只会移动Node所持有的对象。这意味着每个人Node最终都会持有与之前不同的物品。这可能没问题，也可能没问题，具体取决于您的需求。