The first revision is available here and the code is available on GitHub. I modified the method reversePairs
and added mSize
to convert my singly linked list to an array.
Now my main question is the following: do I test all possible types of input for this problem?
SinglyLinkedList
package com.reversell;
public class SinglyLinkedList {
private Node mFirst;
private Node mLast;
private int mSize;
public SinglyLinkedList(Node first) {
this.mFirst = first;
this.mLast = first;
this.mSize = 1;
}
public SinglyLinkedList(int[] array) {
if (array == null || array.length == 0) {
return;
}
this.mFirst = new Node(array[0]);
this.mLast = this.mFirst;
mSize = 1;
for (int i = 1; i < array.length; i++) {
addLast(new Node(array[i]));
}
}
public int getSize() {
return mSize;
}
public void addLast(Node node) {
mLast.setNext(node);
mLast = node;
mSize++;
}
public Node getFirst() {
return mFirst;
}
public Node getLast() {
return mLast;
}
public void print() {
Node current = mFirst;
System.out.print("[");
while (current != null) {
System.out.print(current);
current = current.getNext();
if (current != null) {
System.out.print(", ");
}
}
System.out.print("]");
System.out.println();
}
public void reversePairs() {
// The list is empty or contains one element
if (mFirst == null || mFirst.getNext() == null) {
return;
}
Node temp = null;
Node fop = mFirst;
mFirst = mFirst.getNext();
while (fop != null && fop.getNext() != null) {
if (temp != null) {
// Set the next element of temp, where temp is the predecessor of fop.
temp.setNext(fop.getNext());
}
// 12 -> 34 -> 88
temp = fop.getNext(); // temp == 34
fop.setNext(temp.getNext()); // 12 -> 88
temp.setNext(fop); // 34 -> 12
temp = temp.getNext(); // temp == 12
fop = temp.getNext(); // fop == 88
if (fop == null) {
mLast = temp;
} else {
mLast = fop;
}
}
}
}
Unit tests.
package com.reversell;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import org.junit.Test;
public class SinglyLinkedListTest {
// The list is empty. We don't run the while loop in reversePairs
@Test
public void testEmpty() {
int[] orig = new int[] {};
int[] expected = new int[] {};
SinglyLinkedList linkedList = new SinglyLinkedList(orig);
assertArrayEquals(expected, toArray(reverse(linkedList)));
assertNull(linkedList.getLast());
}
// The list contains one element. We don't run the while loop in reversePairs
@Test
public void testSingleElement() {
int[] orig = new int[] { 12 };
int[] expected = new int[] { 12 };
SinglyLinkedList linkedList = new SinglyLinkedList(orig);
assertArrayEquals(expected, toArray(reverse(linkedList)));
assertEquals(new Node(expected[expected.length - 1]), linkedList.getLast());
}
// The while loop is run once.
// We leave the loop because fop is null. We don't go inside (temp != null)
@Test
public void testTwoElements() {
int[] orig = new int[] { 12, 34 };
int[] expected = new int[] { 34, 12 };
SinglyLinkedList linkedList = new SinglyLinkedList(orig);
assertArrayEquals(expected, toArray(reverse(linkedList)));
assertEquals(new Node(expected[expected.length - 1]), linkedList.getLast());
}
// The while loop is run once.
// We leave the loop because fop.getNext() is null. We don't go inside (temp != null)
@Test
public void testThreeElements() {
int[] orig = new int[] { 12, 34, 78 };
int[] expected = new int[] { 34, 12, 78 };
SinglyLinkedList linkedList = new SinglyLinkedList(orig);
assertArrayEquals(expected, toArray(reverse(linkedList)));
assertEquals(new Node(expected[expected.length - 1]), linkedList.getLast());
}
// The while loop is run more than once.
// We go inside (temp != null).
@Test
public void testFourElements() {
int[] orig = new int[] { 12, 34, 78 };
int[] expected = new int[] { 34, 12, 78 };
SinglyLinkedList linkedList = new SinglyLinkedList(orig);
assertArrayEquals(expected, toArray(reverse(linkedList)));
assertEquals(new Node(expected[expected.length - 1]), linkedList.getLast());
}
private SinglyLinkedList reverse(SinglyLinkedList list) {
list.reversePairs();
return list;
}
private int[] toArray(SinglyLinkedList list) {
int[] arr = new int[list.getSize()];
Node node = list.getFirst();
int index = 0;
while (node != null) {
arr[index++] = node.getData();
node = node.getNext();
}
return arr;
}
}