(Java)

@Test public void test_getMergedList_01() { ListUtilities util = new ListUtilities(); Node leftChain = new Node<>(1, new Node<>(3, new Node<>(5, new Node<>(7, new Node<>(9, null))))); Node rightChain = new Node<>(2, new Node<>(3, new Node<>(5, new Node<>(6, new Node<>(8, null))))); /* * Merging two non-empty chains, each sorted in a non-descending order, * results in a new chain containing elements from both chains and sorted in a non-descending order. * * Assumption: * - Each of the input chains to the getMergedChain method, if not null, is sorted in a non-descending order. */ Node output = util.getMergedChain(leftChain, rightChain); assertTrue(1 == output.getElement()); assertTrue(2 == output.getNext().getElement()); assertTrue(3 == output.getNext().getNext().getElement()); assertTrue(3 == output.getNext().getNext().getNext().getElement()); assertTrue(5 == output.getNext().getNext().getNext().getNext().getElement()); assertTrue(5 == output.getNext().getNext().getNext().getNext().getNext().getElement()); assertTrue(6 == output.getNext().getNext().getNext().getNext().getNext().getNext().getElement()); assertTrue(7 == output.getNext().getNext().getNext().getNext().getNext().getNext().getNext().getElement()); assertTrue(8 == output.getNext().getNext().getNext().getNext().getNext().getNext().getNext().getNext().getElement()); assertTrue(9 == output.getNext().getNext().getNext().getNext().getNext().getNext().getNext().getNext().getNext().getElement()); assertNull(output.getNext().getNext().getNext().getNext().getNext().getNext().getNext().getNext().getNext().getNext()); /* * The input and output chains do not share any node references in common. * i.e., there is no reference aliasing. */ assertTrue(noAliasing(output, leftChain)); assertTrue(noAliasing(output, rightChain)); }

--------------------------------------------------------------------------

private boolean noAliasing(Node n1, Node n2) { Node current1 = n1; Node current2 = n2; boolean found = false; while(current1 != null && !found) { while(current2 != null && !found) { found = current1 == current2; current2 = current2.getNext(); } current1 = current1.getNext(); current2 = n2; } return !found; }

------------------------------------------

public class Node { private E element; private Node next; /* * Constructor */ public Node(E e, Node n) { element = e; next = n; } /* * Accessors */ public E getElement() { return element; } public Node getNext() { return next; } /* * Mutators */ public void setElement(E e) { element = e; } public void setNext(Node n) { next = n; } }