Merge two linked list

Question

Given two linkedlist, merge them. Looking for code review, optimizations and best practices. The code is influenced by feedback here. Changes incorporated were:

1. Linkedlist is no-longer write-only
2. Constructor is not the only way to add new elements
3. HashCode and Equals are more meaningful
4. Merge (non-recursive) function is now eliminating code-duplication

public class MergeLinkedList {
    private Node first;
    private Node last;
    private int size;

    MergeLinkedList(List<Integer> items) {
        for (Integer i : items) {
            add(i);
        }
    }

    public void add (int val) {
        final Node newNode = new Node(val);
        if (first == null) {
            first = last = newNode;
        } else {
            last.next = newNode;
            last = last.next;
        }
        size++;
    }

    private static class Node {
        private int item;
        private Node next;

        Node(int element) {
            this.item = element;
        }
    }

    private Node mergeLinkedListRecursive(Node node1, Node node2) {
        if (node1 == null) {
           return node2; 
        }

        if (node2 == null) {
            return node1;
        }

        if (node1.item < node2.item) {
            node1.next = mergeLinkedListRecursive(node1.next, node2);
            return node1;
        } else {
            node2.next = mergeLinkedListRecursive(node1, node2.next);
            return node2;
        }
    }

    public void mergeLinkedListRecursion(MergeLinkedList list2) {
        if (list2 == null) {
            return;
        }
        first = mergeLinkedListRecursive(first, list2.first);
    }

    private void mergeLinkedList(Node node1, Node node2) {
        if (node1 == null) {
            first = node2;
            return;
        }

        if (node2 == null) {
            first = node1;
            return;
        }

        Node prev = null;
        Node aux = null;

        while (node1 != null && node2 != null) {
            if (node1.item < node2.item) {
                aux = node1;
                node1 = node1.next;

            } else {
                aux = node2;
                node2 = node2.next;
            }

            if (prev == null) {
                first = prev = aux;
            } else {
                prev.next = aux;
                prev = prev.next;
            }
        }
        prev.next = node1 != null ? node1 : node2;
    }

    public void mergeLinkedList(MergeLinkedList list2) {
        if (list2 == null) {
            return;
        }
        mergeLinkedList(this.first, list2.first);
    }

    public int[] toArray() {
        int[] items = new int[size];
        int i = 0;
        for (Node x = first; x != null; x = x.next) {
            items[i++] = x.item;
        }
        return items;
    }

    @Override
    public int hashCode() {
        int hashCode = 1;
        for (Node x = first; x != null; x = x.next)
            hashCode = 31*hashCode + (x == null ? 0 : x.hashCode());
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        MergeLinkedList other = (MergeLinkedList) obj;
        Node currentListNode = first; 
        Node otherListNode =  other.first;

        while (currentListNode != null && otherListNode != null) {
            if (currentListNode.item != otherListNode.item) return false;
            currentListNode = currentListNode.next;
            otherListNode = otherListNode.next;
        }
        return currentListNode == null && otherListNode == null;
    }
}



public class MergeLinkedListTest {

    @Test
    public void testDifferentSizeListRecurse() {
        MergeLinkedList l1 = new MergeLinkedList(Arrays.asList(1, 3, 5));
        MergeLinkedList l2 = new MergeLinkedList(Arrays.asList(2, 4));
        l1.mergeLinkedListRecursion(l2);

        MergeLinkedList expected1 = new MergeLinkedList(Arrays.asList(1, 2, 3, 4, 5));
        assertTrue(expected1.equals(l1));
    }

    @Test
    public void testSameSizeListRecurse() {
        MergeLinkedList l1 = new MergeLinkedList(Arrays.asList(1, 2, 3));
        MergeLinkedList l2 = new MergeLinkedList(Arrays.asList(5, 6, 7));
        l1.mergeLinkedListRecursion(l2);

        MergeLinkedList expected1 = new MergeLinkedList(Arrays.asList(1, 2, 3, 5, 6, 7));
        assertTrue(expected1.equals(l1)); 
    }

    @Test
    public void testNullListRecurse() {
       MergeLinkedList l1 = new MergeLinkedList(Arrays.asList(1, 2, 3));
       MergeLinkedList l2 = new MergeLinkedList(new ArrayList<Integer>());
       l1.mergeLinkedListRecursion(l2);

       MergeLinkedList expected1 = new MergeLinkedList(Arrays.asList(1, 2, 3));
       assertTrue(expected1.equals(l1));
    }

    @Test
    public void testDifferentSizeList() {
        MergeLinkedList l1 = new MergeLinkedList(Arrays.asList(1, 3, 5));
        MergeLinkedList l2 = new MergeLinkedList(Arrays.asList(2, 4));
        l1.mergeLinkedList(l2);

        MergeLinkedList expected1Recurse = new MergeLinkedList(Arrays.asList(1, 2, 3, 4, 5));
        assertTrue(expected1Recurse.equals(l1));
    }

    @Test
    public void testSameSizeList() {
        MergeLinkedList l1 = new MergeLinkedList(Arrays.asList(1, 2, 3));
        MergeLinkedList l2 = new MergeLinkedList(Arrays.asList(5, 6, 7));
        l1.mergeLinkedList(l2);

        MergeLinkedList expected1Recurse = new MergeLinkedList(Arrays.asList(1, 2, 3, 5, 6, 7));
        assertTrue(expected1Recurse.equals(l1));
    }

    @Test
    public void testNullList() {
       MergeLinkedList l1 = new MergeLinkedList(Arrays.asList(1, 2, 3));
       MergeLinkedList l2 = new MergeLinkedList(new ArrayList<Integer>());
       l1.mergeLinkedList(l2);

       MergeLinkedList expected1Recurse = new MergeLinkedList(Arrays.asList(1, 2, 3));
       assertTrue(expected1Recurse.equals(l1));
    }

}

Answer 1

Wow! You've obviously put a lot of work into this!

Advice / Optimizations

1. Unless it's an explicit requirement of the assignment, there's no reason you can't use java.util.LinkedList.
2. I think it's cleaner to have the mergeLinkedLists method live in a different class from the linked list. In other words, the linked list is a completely reusable container for data, and the customizations live somewhere else.
3. If you want to get fancy you can use generics so that this class can operate on any Object, not just Integer. (This should be considered "extra credit," not a critique of your program.)

This is how I would write it. (This is likely a school assignment so I'm just supplying a skeleton.)

public class Merge {

    private Merge() { } // no public constructor

    public static List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        List<Integer> returnVal = new LinkedList<>();

        if (list1 == null && list2 == null) {
            // both lists null.  What to return?  Or throw exception.
        }
        if (list1 == null) {
            // What to return?  Or throw exception.
        }
        if (list2 == null) {
            // What to return?  Or throw exception.
        }

        // do merging
        while (!list1.isEmpty() && !list2.isEmpty()) {
            // We know that both lists must have at least one element.
            // 1. Figure out which list has the smaller element.
            // 2. Remove that item from its list.
            // 3. Add that item to the end of returnVal
        }

        // Now one or both lists are empty.
        // Those items have to be added to "returnVal" as well.

        return returnVal;
    }

    public static List<Integer> mergeRecursive(List<Integer> list1, List<Integer> list2) {
        // do stuff
    }
}

Stupid Picky Stuff

1. You don't need to have a name like mergeLinkedListRecursion if the parameter is already of type LinkedList. You can just call it mergeRecursion. Anybody reading it will understand that it operates on linked lists.
2. I don't get why you have functions with names of "recursive", "recursion", and "recurse". It seems to me it would be cleaner to use one verb form for all your functions.