Java: LinkedList binding in pieces

Question

If you are given the head of a linked list and are asked to cancel each sequence of nodes, how can this be done in Java? e.g. a->b->c->d->e->f->g->h with k = 3 will be c->b->a->f->e->d->h->g->f

Any general help or even pseudo-code is welcome! Thanks!

Answer 1

If k expected to be small enough, I would just ask for the simplest thing: ignore the fact that this is a linked list in general, and consider each subsequence as a thing like an array of things to reverse.

So, if your linked list of node class is Node<T> , create a Node<?>[] Of size k . For each segment, load k Nodes into the list of arrays, and then simply change their elements to a simple for loop. In pseudo code:

 // 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, uses an easily recognizable reversal algorithm.

Cons: requires an array of k (only once since you can reuse it per segment)

Also note that this means that each Node does not move in the list, only Node objects are saved. This means that each Node will contain a different element than before. It may or may not be good, depending on your needs.

Answer 2

This is a fairly high level, but I think that it will give some recommendations.

I will have a helper method, for example void swap3(Node first, Node last) , which takes three elements at an arbitrary position in the list and cancels them. This should not be difficult, and this could be done recursively (replace the outer elements, write down the inner elements until the list size is 0 or 1). Now that I think about it, you can easily generalize this to swapK() if you use recursion.

Once this is done, you can just go through the linked list and call swapK() every k nodes. If the size of the list is not divisible by k , you can either simply not change this last bit, or cancel the last nodes of length%k using the swap technique.

Answer 3

TIME O (n); SPACE O (1)

A common requirement of enumerating a list is that you do this in O (n) time and O (1) space. This excludes recursion or stack or temporary array (what if K == n?) Etc. Therefore, the challenge here is to change the in-place reversal algorithm to account for factor K Instead of K I use dist for distance.

Here is a simple in-place reversal algorithm: use three pointers to view the list: b to point to the title of the new list; c to indicate the moving head of the raw list; a to facilitate the exchange 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 ^ ^ | | bc `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 the simpleReverse algorithm, follow these steps:

1] After reversing the first fragment, set head to b ; head is a constant heading for the resulting list.

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

some other details:

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

4] use the cnt counter to track when dist consecutive nodes have been canceled.

5] use the tail variable to track the entire processed fragment and tmp to track the tail of the processed fragment.

6] note that before processing the piece, the head, which should become its tail, is the first node that 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 } 

Answer 4

eg. 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))))) 

different example. 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 

Answer 5

Use the stack and recursively remove k items from the list, insert them on the stack, and then put them in and add them in place. Not sure if this is the best solution, but stacks offer the right way to flip things around. Note that this also works if you had a queue instead of a list. Just remove the k elements, push them onto the stack, pull them from the stack and leave them in the queue :)

Answer 6

This implementation uses the ListIterator class:

 LinkedList<T> list; //Inside the method after the method 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); }