3
\$\begingroup\$

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; } }
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

My first impressions:

  • There is altogether too much code, and it's too confusing.
  • Your SinglyLinkedList class should not expose Nodes in its interface.
  • If there is just one method to add a node to a singly-linked list, it should be addFirst() rather than addLast(). (Manipulating the end of the list efficiently requires that you maintain an mLast pointer, which is an unnecessary complication. Minimalism is crucial for interview situations.)
  • Instead of print(), it would be more idiomatic to define toString().

"Raw" vs. "polished" linked lists

There are two styles of linked lists.

The simple kind exposes the list nodes as the interface. For an example of this, see Reversing k-sized sequences in a linked list. (This node-swapping question is a specific case of that problem where k = 2.) The user just manipulates pointers as necessary. There is no additional bookkeeping for, say, the size of the list.

In contrast, the Java LinkedList class presents a data structure where the nodes are an implementation detail that is hidden from the user.

What you have done, though, is a dangerous hybrid. By accepting and returning Nodes, you make is possible for other code to manipulate the node pointers behind your back, possibly rendering your mLast and mSize inconsistent.

Therefore, your method signatures should be designed such that they only accept and return ints, not Nodes.

Simplification

The problem can be solved without keeping track of mLast and mSize, so you should drop them. Then you no longer need to worry whether reversePairs() sets mLast correctly.

You can eliminate special cases by introducing a dummy node. In particular, a dummy node would let you get rid of the special handling for array[0] (and the special handling for an empty array). It would also make it impossible for mFirst to be null, thus eliminating that special case from reversePairs().

fop and temp aren't exactly variable names that make sense. temp, in particular, is almost always a horrible name that can be improved. In my solution below, I've defined a, b, c, and d up front for each iteration, and it's very simple to just adjust their next pointers.

public class SinglyLinkedList { /** Dummy node */ private final Node head = new Node(0); public SinglyLinkedList(int[] array) { for (int i = array.length - 1; i >= 0; i--) { this.addFirst(array[i]); } } public void addFirst(int datum) { Node n = new Node(datum); n.setNext(this.head.getNext()); this.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() { StringBuilder s = new StringBuilder("["); for (Node n = this.head.getNext(); n != null; n = n.getNext()) { s.append(n); s.append(", "); } if (s.length() >= 2) s.setLength(s.length() - 2); // Remove final ", " return s.append(']').toString(); } }
\$\endgroup\$
5
  • \$\begingroup\$ Thank you very much! Your code is clean and simple. As to print(), I totally forgot about toString(). You know... When you think of something complicated, you forget simple things. \$\endgroup\$ Commented Jul 25, 2015 at 13:19
  • \$\begingroup\$ About the two styles of linked lists. If I understand you correctly, the first implementation style doesn't contain two distinct classes: Node and LinkedList. There I personally would use the static method makeList rather than the constructor because the second parameter of the constructor contains is a LinkedListNode variable which should also be constructes, and, in its turn, contains its own next in its constructor. E.g., LinkedListNode<Integer> linkedListNode = new LinkedListNode<Integer>(1, new LinkedListNode<Integer>(3, null)); \$\endgroup\$ Commented Jul 25, 2015 at 18:46
  • \$\begingroup\$ Thank you for the simplification suggestions. fop meant the first in a pair. \$\endgroup\$ Commented Jul 26, 2015 at 14:10
  • \$\begingroup\$ I posted the third round of code review. \$\endgroup\$ Commented Jul 26, 2015 at 14:39
  • 1
    \$\begingroup\$ Yes, I think you have understood me correctly. \$\endgroup\$ Commented Jul 26, 2015 at 18:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.