CODEWITHSUNDEEP
javaalgorithm
OckhamsRazor
OckhamsRazor

Reputation: 4906

Java: LinkedList reversal in chunks

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!

Upvotes: 6

Views: 1340

Answers (6)

BLUEPIXY
BLUEPIXY

Reputation: 40145

E.g. by Common Lisp

(defun rev-k (k sq)
  (if (<= (length sq) k)
      (reverse sq)
      (concatenate 'list (reverse (subseq sq 0 k)) (rev-k k (subseq sq k)))))

other way E.g. by F# use Stack

open System.Collections.Generic
let rev_k k (list:'T list)  =
  seq {
    let stack = new Stack<'T>()
    for x in list do
      stack.Push(x)
      if stack.Count = k then
        while stack.Count > 0 do
          yield stack.Pop()
    while stack.Count > 0 do
      yield stack.Pop()
  }
  |> Seq.toList

Upvotes: 1

kasavbere
kasavbere

Reputation: 6003

TIME O(n); SPACE O(1)

A usual requirement of list reversal is that you do it in O(n) time and O(1) space. This eliminates recursion or stack or temporary array (what if K==n?), etc. Hence the challenge here is to modify an in-place reversal algorithm to account for the K factor. Instead of K I use dist for distance.

Here is a simple in-place reversal algorithm: Use three pointers to walk the list in place: b to point to the head of the new list; c to point to the moving head of the unprocessed list; a to facilitate swapping between b and c.

 A->B->C->D->E->F->G->H->I->J->L //original
 A<-B<-C<-D    E->F->G->H->I->J->L //during processing
          ^    ^
          |    |
          b    c
 `a` is the variable that allow us to move `b` and `c` without losing either of
  the lists.

Node simpleReverse(Node n){//n is head
if(null == n || null == n.next)
   return n;
Node a=n, b=a.next, c=b.next;
a.next=null; b.next=a;
while(null != c){
   a=c;
   c=c.next;
   a.next=b;
   b=a;
}
return b;
}

To convert the simpleReverse algorithm to a chunkReverse algorithm, do following:

1] After reversing the first chunk, set head to b; head is the permanent head of the resulting list.

2] for all the other chunks, set tail.next to b; recall that b is the head of the chunk just processed.

some other details:

3] If the list has one or fewer nodes or the dist is 1 or less, then return the list without processing.

4] use a counter cnt to track when dist consecutive nodes have been reversed.

5] use variable tail to track the tail of the chunk just processed and tmp to track the tail of the chunk being processed.

6] notice that before a chunk is processed, it's head, which is bound to become its tail, is the first node you encounter: so, set it to tmp, which is a temporary tail.

public Node reverse(Node n, int dist) {
  if(dist<=1 || null == n || null == n.right) 
      return n;
  Node tail=n, head=null, tmp=null;
  while(true) {
      Node a=n, b=a.right; n=b.right;
      a.right=null; b.right=a;
      int cnt=2;
      while(null != n && cnt < dist) {
          a=n; n=n.right; a.right=b; b=a;
          cnt++;
      }
      if(null == head) head = b;
      else {
          tail.right=b;tail=tmp;
      }
      tmp=n;
      if(null == n) return head;
      if(null == n.right) {
          tail.right=n;
          return head;
      }
  }//true
  }

Upvotes: 1

Nata
Nata

Reputation: 1

This implementation uses ListIterator class:

LinkedList<T> list;
//Inside the method after the method's parameters check
ListIterator<T> it = (ListIterator<T>) list.iterator(); 
ListIterator<T> reverseIt =  (ListIterator<T>) list.listIterator(k); 

for(int i = 0; i< (int) k/2; i++ )
{
    T element  = it.next();
    it.set(reverseIt.previous());
    reverseIt.set(element);
}

Upvotes: 0

Samy Arous
Samy Arous

Reputation: 6814

Use a stack and recursively remove k items from the list, push them to the stack then pop them and add them in place. Not sure if it's the best solution, but stacks offer a proper way of inverting things. Notice that this also works if instead of a list you had a queue. Simply dequeue k items, push them to the stack, pop them from the stack and enqueue them :)

Upvotes: 0

yshavit
yshavit

Reputation: 43401

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.

Upvotes: 4

Peter
Peter

Reputation: 1359

This is pretty high-level, but I think it'll give some guidance.

I'd have a helper method like void swap3(Node first, Node last) that take three elements at an arbitrary position of the list and reverses them. This shouldn't be hard, and could could be done recursively (swap the outer elements, recurse on the inner elements until the size of the list is 0 or 1). Now that I think of it, you could generalize this into swapK() easily if you're using recursion.

Once that is done, then you can just walk along your linked list and call swapK() every k nodes. If the size of the list isn't divisble by k, you could either just not swap that last bit, or reverse the last length%k nodes using your swapping technique.

Upvotes: 1

Related Questions