Reverse sublists of a linked list

Question

This code reverses each consecutive n elements of a linked list, and for spare nodes, leaves them as they are.

For example, the linked list

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

for an interval of 3 should result in

3 -> 2 -> 1-> 6 -> 5 -> 4 -> 7

Note that 7 is left as it is as its spare.

I'm looking for code review, optimization and best practices.

   public class ReverseAtInterval<T> implements Iterable<T> {

        private Node<T> first; 
        private Node<T> last;
        private int size;


        public ReverseAtInterval(List<T> c) {
            for (T item : c) {
                add(item);
            }
        }

        public void add (T t) {
            final Node<T> l = last;
            final Node<T> node = new Node<T>(t, null);
            last = node;
            if (first == null) {
                first = node;
            } else {
                l.next = node;
            }
            size++;
        }

        private static class Node<T> {
            T item;
            Node<T> next;

            Node(T item, Node<T> next) {
                this.item = item;
                this.next = next;
            }
        }

        private static class ReversedFirstLastNextData<T> {
            Node<T> first;  // first node in the reversed list.
            Node<T> last;   // last node in the reversed list.
            Node<T> next;   // next node - this node is not a part of revered list

            public ReversedFirstLastNextData(Node<T> first, Node<T> last, Node<T> next) {
                this.first = first;
                this.last = last;
                this.next = next;
            }
        }


        private ReversedFirstLastNextData<T> reverse(Node<T> start, int n) {
            Node<T> prev = null;
            Node<T> ptr = start;
            Node<T> ptr1 = null;

            int ctr = 0;

            while (ctr < n) {
                ptr1 = ptr.next;
                ptr.next = prev;

                // advance forward.
                prev = ptr;
                ptr = ptr1;

                ctr++; 
            }

            return new ReversedFirstLastNextData<T>(prev, start, ptr);
        }



        public void reverseAtInterval(int n) {
            int ctr = 0;
            ReversedFirstLastNextData<T> prev = null;
            ReversedFirstLastNextData<T> current = null;
            Node<T> inputNode = first;

            while (ctr < (size/n)) {
                current = reverse(inputNode, n);

                if (prev == null) {
                    first = current.first;
                } else {
                    prev.last.next = current.first;
                }

                inputNode = current.next;
                prev = current;

                ctr++;
            }

            current.last.next = current.next;
        }

        @Override
        public Iterator<T> iterator() {
            return new LinkedListItr();
        }   

        private class LinkedListItr implements Iterator<T> {
            private Node<T> prev;
            private Node<T> current;
            private int currentSize = 0;
            private int initialCapacity;

            public LinkedListItr() {
                this.current  = first;
                this.currentSize = 0;
                initialCapacity = size;
            } 


            @Override
            public boolean hasNext() {
                return currentSize < size;
            }

            @Override
            public T next() {
                if (initialCapacity != size) {
                    throw new ConcurrentModificationException();
                }

                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                currentSize++;
                prev = current;
                T item = current.item;
                current = current.next;
                return item;
            }

            @Override
            public void remove() {
                if (initialCapacity != size) {
                    throw new ConcurrentModificationException();
                }
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                prev.next = current.next;
                size--;
                initialCapacity--;
            }
        }


        public List<T> toArray() {
            List<T> list = new ArrayList<T>();
            Node<T> ptr = first;
            while (ptr != null) {
                list.add(ptr.item);
                ptr = ptr.next;
            }
            return list;
        }

    }


public class ReverseAtIntervalTest {

    @Test
    public void testEven() {
        ReverseAtInterval<Integer> rai = new ReverseAtInterval<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8));
        rai.reverseAtInterval(4);
        assertEquals(Arrays.asList(4, 3, 2, 1, 8, 7, 6, 5), rai.toArray());
    }

    @Test
    public void testOdd() {
        ReverseAtInterval<Integer> rai = new ReverseAtInterval<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8));
        rai.reverseAtInterval(3);
        assertEquals(Arrays.asList(3, 2, 1, 6, 5, 4, 7, 8), rai.toArray());
    }

}

Answer 1

You and @bazang are both very much into interview-questions, and I think you would benefit greatly from answering each others' questions. In fact, writing reviews would be more useful for preparing you for interviews than asking yet more questions, because:

• You get "no" choice in the matter of which question you are presented — just like in a real interview (assuming you commit yourself to answering whatever question comes your way).
• You practice communication skills, which are also important for interviewing.
• When you review someone else's work, you gain an appreciation for what goes on in the mind of the interviewer.

I bring this up now, because @bazang has tried to solve… exactly the same problem!

---

Review

I agree with @Anonymous that your architecture is much too complicated, with too many inner classes.

It's odd that your ReverseAtInterval() constructor takes a List<T>, but you also offer the option to add individual elements via public add(T). The state problem was to reverse a list — so don't complicate things by offering to handle more stuff.

Passing the list to the ReverseAtInterval() constructor, then passing the interval to .reverseAtInterval() is also odd. Calling .reverseAtInterval() will rearrange everything in the new order. Allowing that mutated list to be further mutated if one calls .reverseAtInterval() again is more likely to be misused than useful.

If you try to reverse a list with an interval that is greater than the length of the input list, you get a NullPointerException.

.toArray() is misnamed. I would expect it to return an array, not a List.

---

Proposed Solution

Here's what I came up with. (It's completely different from the solution for @bazang because you chose to base your interface on java.util.List.)

ReverseAtInterval.java

import java.util.*;

public class ReverseAtInterval<T> implements Iterable<T> {
    private final List<T> list;
    private final int interval;

    public ReverseAtInterval(List<T> list, int interval) {
        if (interval < 1) throw new IllegalArgumentException("interval < 1");
        this.list = list;
        this.interval = interval;
    }

    public Iterator<T> iterator() {
        return new SublistReversingIterator();
    }

    //////////////////////////////////////////////////////////////////////

    private class SublistReversingIterator implements Iterator<T> {
        // Iterator for the underlying list
        private final Iterator<T> underIter = ReverseAtInterval.this.list.listIterator();
        private final LinkedList<T> group = new LinkedList<T>();
        private Iterator<T> groupIter = group.iterator();

        public boolean hasNext() {
            return this.groupIter.hasNext() || this.underIter.hasNext();
        }

        public T next() {
            if (!this.groupIter.hasNext()) {
                if (!this.underIter.hasNext()) {
                    throw new NoSuchElementException();
                }

                try {
                    for (int i = interval; i > 0; i--) {
                        this.group.push(this.underIter.next());
                    }
                    this.groupIter = group.iterator();
                } catch (NoSuchElementException exhausted) {
                    // For spare nodes, leave them as they are.  In other
                    // words, reverse the group again to restore the original
                    // order.
                    this.groupIter = group.descendingIterator();
                }
            }

            try {
                return groupIter.next();
            } finally {
                groupIter.remove();
            }
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

ReverseAtIntervalTest.java

import static java.lang.System.out;

public class ReverseAtIntervalTest {

    public static void main(String[] args) {
        List<Integer> oneFive = Arrays.asList(new Integer[] {1, 2, 3, 4, 5});
        for (int interval = 1; interval <= 6; interval++) {
            for (int elem : new ReverseAtInterval<Integer>(oneFive, interval)) {
                out.print(elem); out.print(' ');
            }
            out.println();
        }
        // IllegalArgumentException expected...
        new ReverseAtInterval<Integer>(oneFive, 0);
    }
}

Answer 2

Architecture

This is much more complicated than it needs to be. There's no need to define a custom list class, unless you want to practice low-level destructive list-munging. Use one of the standard classes, like java.util.LinkedList.

It's simpler to attack this problem in two parts:

1. Divide the list into sublists.

2. Reverse them and concatenate them.

This can be quite simple — it's one line of Clojure:

(defn reverse-sublists [n xs] (mapcat reverse (partition n n nil xs)))

In Java you need to write the partitioning and concatenating code yourself, but this is still much simpler than defining your own list class.

Comments on the custom-list implementation

If you do want to define a custom list class and reverse the list destructively, there are some things that could be done better:

ReverseAtInterval is misnamed. Its instances aren't reversals; they're linked lists, so it should be called something like LinkedList (or SinglyLinkedList to avoid colliding with java.util.LinkedList). Classes should be named for what their instances represent, not for the problem they solve.

reverse does something not obvious: it reverses the first n elements, not the whole list. This should be reflected in its name: something like reverseFirstN or reversePrefix.

reverse is an operation on a list, not on a ReversedFirstLastNextData, so it should not be a method of ReversedFirstLastNextData.

ReversedFirstLastNextData is unnecessary. next is always last->next, and last is always known to the caller (it was start), so reverse only needs to return first.

Variables in reverse:

• ctr should be a for-loop variable, to make it clear how it's updated. It's OK to call it i.
• ptr1 can be declared inside the loop.
• ptr and ptr1 should have meaningful names, such as current and next.

ConcurrentModificationException is usually about concurrent modification in multiple threads. That's not what you're using it for. AFAICT you're making sure ReverseAtInterval.add wasn't called, which can be done directly by making it private. If you still want to check to make sure you didn't mess it up, there's a simpler way:

assert initialCapacity == size;

The parentheses in ctr < (size/n) are redundant. Java arithmetic has higher precedence than comparisons. You can rely on this.