Java: LinkedList reversal in chunks

algorithm, java

Solution

If `k` is expected to be reasonably small, I would just go for the simplest thing: ignore the fact that it's a linked list at all, and treat each subsequence as just an array-type thing of things to be reversed.

So, if your linked list's node class is a `Node<T>`, create a `Node<?>[]` of size `k`. For each segment, load `k` `Nodes` into the array list, then just reverse their elements with a simple `for` loop. In pseudocode:

// 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

Pros: very simple, O(N) performance, takes advantage of an easily recognizable reversing algorithm.

Cons: requires a `k`-sized array (just once, since you can reuse it per segment)

Also note that this means that each `Node` doesn't move in the list, only the objects the `Node` holds. This means that each `Node` will end up holding a different item than it held before. This could be fine or not, depending on your needs.

Problem

If you are provided the head of a linked list, and are asked to reverse every k sequence of nodes, how might this be done in Java? e.g., `a->b->c->d->e->f->g->h` with k = 3 would be `c->b->a->f->e->d->h->g->f` Any general help or even pseudocode would be greatly appreciated! Thanks!

Original source