• 1

• 1.4k
• 3
• 15
• 29

• 1.4k
• 3
• 15
• 29

Here is the source of the question.

The solution on GitHub.

Revision 1.

Revision 2.

Revision 3.

@200_success' suggestions from revision 3:

• The iterator's next() will throw a NoSuchElementException if we run off the last element of the list while iterating.
• Iterator.remove() is implemented.
• The implementation of SinglyLinkedList.toString() is more straightforward.

My changes:

• toArray and size for tests.
• I made Node a static nested class of SinglyLinkedList as they do with Entry in the Java LinkedList class. It allowed me not to implement setNext, getNext, and getData of Node. Anyway, Node not accessible for client code. So I think I can access members of Node directly, and it's not dangerous.

The questions I have now:

1. Do my tests cover all the edge cases of the algorithm? See SinglyLinkedList.reversePairs() and SinglyLinkedListTest.
2. Do I need to null out the reference to cur in my iterator's remove() method?
3. Why would I need SinglyLinkedList.equals() which was suggested here?

SinglyLinkedList

package com.singlylinkedlist;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class SinglyLinkedList implements Iterable<Integer> {
 /** Dummy node */
 private final Node head = new Node(0);
 private int size;
 public SinglyLinkedList(int[] data) {
 for (int i = data.length - 1; i >= 0; i--) {
 addFirst(data[i]);
 }
 }
 public void addFirst(int datum) {
 Node n = new Node(datum);
 n.next = head.next;
 head.next = n;
 size++;
 }
 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.next) != null && (c = b.next) != null) {
 Node d = c.next;
 a.next = c;
 c.next = b;
 b.next = d;
 a = b;
 }
 }
 
 public int[] toArray() {
 int array[] = new int[size];
 int i = 0;
 Iterator<Integer> iterator = iterator();
 while(iterator.hasNext()) {
 array[i++] = iterator.next();
 }
 return array;
 }
 @Override
 public String toString() {
 Iterator<Integer> iterator = iterator();
 if (!iterator.hasNext()) {
 return "[]";
 }
 
 StringBuilder s = new StringBuilder("[" + iterator.next());
 while(iterator.hasNext()) {
 int nodeValue = iterator.next();
 s.append(" -> " + nodeValue);
 }
 return s.append(']').toString();
 }
 @Override
 public Iterator<Integer> iterator() {
 return new Iterator<Integer>() {
 Node prev;
 Node current = head;
 Node next = current.next;
 @Override
 public void remove() {
 prev.next = next;
 current.next = null;
 current = null; // TODO: Do I need to eliminate this obsolete reference?
 current = next;
 if (current == null) {
 next = null;
 } else {
 next = current.next;
 }
 }
 @Override
 public Integer next() {
 if (!hasNext()) {
 throw new NoSuchElementException();
 }
 prev = current;
 current = next;
 next = next.next;
 return current.data;
 }
 @Override
 public boolean hasNext() {
 return next != null;
 }
 };
 }
 
 private static class Node {
 Node next;
 int data;
 Node(int data) {
 this.data = data;
 }
 @Override
 public boolean equals(Object obj) {
 if (obj == this) {
 return true;
 }
 if (!(obj instanceof Node)) {
 return false;
 }
 Node another = (Node) obj;
 return data == another.data;
 }
 @Override
 public int hashCode() {
 int result = 17;
 result = 31 * result + data;
 return result;
 }
 }
}

SinglyLinkedListTest

package com.singlylinkedlist;
import org.junit.Assert;
import org.junit.Test;
public class SinglyLinkedListTest {
 @Test
 public void testEmpty() {
 int[] orig = new int[] {};
 int[] reversed = new int[] {};
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void testSingle() {
 int[] orig = new int[] { 1 };
 int[] reversed = new int[] { 1 };
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void testLoopOnce() {
 int[] orig = new int[] { 1, 2 };
 int[] reversed = new int[] { 2, 1 };
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void testLoopMoreThanOnce() {
 int[] orig = new int[] { 1, 2, 3, 4, 5, 6 };
 int[] reversed = new int[] { 2, 1, 4, 3, 6, 5 };
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
}