Here is the source of the question.
When I started the second round of code review, I wanted to make sure that I had included all the possible input types. However, I received many useful suggestions from @200_success.
I took some time to learn them, and now I want to post my code again.
In this revision:
- The class
SinglyLinkedList
no longer exposes node pointers.getNext
of the classNode
returning the pointer to the next element is package-private.SinglyLinkedList
can use it, and client code can't. - I don't maintain
mLast
which is unnecessary for a short interview problem. If I was told to prepend and append items, I would needmFirst
andmLast
. - I deleted
mSize
which was only used fortoArray
- I wrote new tests which (I think) cover all the edge cases of 200_success' algorithm.
- I don't use
toArray
for testing. I use a copy constructor to make a copy of an original list before reversing. Each list has an iterator. I compare values of the two lists iterating over them. If I usedtoArray
, I would create two arrays (one from an original list and one from its reversed version) which would mean twice as much memory as I use.
Node
package com.singlylinkedlist;
class Node {
private Node next;
private int data;
Node(int data) {
this.data = data;
}
int getData() {
return data;
}
void setNext(Node n) {
this.next = n;
}
Node getNext() {
return next;
}
}
SinglyLinkedList.
package com.singlylinkedlist;
import java.util.Iterator;
public class SinglyLinkedList implements Iterable<Integer> {
/** Dummy node */
private final Node head = new Node(0);
public SinglyLinkedList(int[] data) {
for (int i = data.length - 1; i >= 0; i--) {
addFirst(data[i]);
}
}
public SinglyLinkedList(SinglyLinkedList from) {
Node source = from.head.getNext();
Node dst = head;
while (source != null) {
dst.setNext(new Node(source.getData()));
source = source.getNext();
dst = dst.getNext();
}
}
public void addFirst(int datum) {
Node n = new Node(datum);
n.setNext(head.getNext());
head.setNext(n);
}
public void reversePairs() {
// For each loop iteration, transform
//
// maybe null --+
// |
// v
// Original: (a) -> b -> c -> d ...
// To: a -> c -> (b) -> d ...
// ^
// |
// +-- becomes "a" of the next iteration
Node a = this.head, b, c;
while ((b = a.getNext()) != null && (c = b.getNext()) != null) {
Node d = c.getNext();
a.setNext(c);
c.setNext(b);
b.setNext(d);
a = b;
}
}
@Override
public String toString() {
Iterator<Integer> iterator = iterator();
if (!iterator.hasNext()) {
return "[]";
}
StringBuilder s = new StringBuilder("[");
while(true) {
int nodeValue = iterator.next();
s.append(nodeValue);
if (!iterator.hasNext()) {
return s.append(']').toString();
}
s.append(" -> ");
}
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node current = head;
@Override
public void remove() {
throw new UnsupportedOperationException();
}
@Override
public Integer next() {
current = current.getNext();
return current.getData();
}
@Override
public boolean hasNext() {
return current.getNext() != null;
}
};
}
}
Unit tests.
package com.singlylinkedlist;
import org.junit.Assert;
import org.junit.Test;
import java.util.Iterator;
public class SinglyLinkedListTest {
@Test
public void testEmpty() {
doReverse(new int[] {});
}
@Test
public void testSingle() {
doReverse(new int[] { 1 });
}
@Test
public void testLoopOnce() {
doReverse(new int[] { 1, 2 });
}
@Test
public void testLoopMoreThanOnce() {
doReverse(new int[] { 1, 2, 3, 4, 5, 6 });
}
private void doReverse(int[] data) {
SinglyLinkedList orig = new SinglyLinkedList(data);
SinglyLinkedList copy = new SinglyLinkedList(orig);
orig.reversePairs();
Iterator<Integer> origIterator = orig.iterator();
Iterator<Integer> copyIterator = copy.iterator();
// The list is empty
if (!origIterator.hasNext()) {
return;
}
int origFirstInPair = origIterator.next();
int copyFirstInPair = copyIterator.next();
while (true) {
if (!origIterator.hasNext()) {
Assert.assertTrue(origFirstInPair == copyFirstInPair);
return;
}
int origSecondInPair = origIterator.next();
int copySecondInPair = copyIterator.next();
Assert.assertTrue(origFirstInPair == copySecondInPair && origSecondInPair == copyFirstInPair);
if (!origIterator.hasNext()) {
return;
}
origFirstInPair = origIterator.next();
copyFirstInPair = copyIterator.next();
}
}
}