Code to merge sorted linked lists in java

Question

Since I am using Hackerrank codepair, I have to resort to inner classes. Please review the code and let me know if this can be improved.

import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class LinkedListMerge {

    private List<LinkedList<Integer>> listsToMerge;
    private LinkedList<Integer> mergedList;

    public LinkedListMerge() {
        listsToMerge = new ArrayList<LinkedList<Integer>>();
        listsToMerge.add(new LinkedList(new Integer[]{3, 5, 7, 10, 11}));
        listsToMerge.add(new LinkedList(new Integer[]{13, 25, 72, 101, 111}));
        listsToMerge.add(new LinkedList(new Integer[]{12, 15, 17, 110, 112}));

        mergedList = new LinkedList<Integer>();
    }

    public void mergeLists() {
        PriorityQueue<ValueIterator> priorityQueue = new PriorityQueue<ValueIterator>(listsToMerge.size());

        for(LinkedList<Integer> linkedList : listsToMerge) {
            Iterator<Node<Integer>> currentIterator = linkedList.iterator();
            priorityQueue.add(new ValueIterator(currentIterator.next().getValue(), currentIterator));
        }

        while(priorityQueue.peek() != null) {
            ValueIterator minElement = priorityQueue.poll();
            mergedList.add((Integer)minElement.getValue());
            if(minElement.getIterator().hasNext()) {
                Node<Integer> nextElement = ( Node<Integer>)minElement.getIterator().next();
                priorityQueue.add(new ValueIterator(nextElement.getValue(), minElement.getIterator()));
            }
        }

    }

    public LinkedList getMergedList() {
        return mergedList;
    }

    private class ValueIterator<K extends Comparable> implements Comparable {
        K value;
        Iterator<K> iterator;

        public ValueIterator(K value, Iterator<K> iterator) {
            this.value = value;
            this.iterator = iterator;
        }

        public K getValue() {
            return value;
        }

        public Iterator<K> getIterator() {
            return iterator;
        }

        @Override 
        public int compareTo(Object o) {
            return value.compareTo(((ValueIterator)o).getValue());
        }
    }

    public class LinkedList<K extends Comparable> {
        private Node<K> head = null;
        private Node<K> tail = null;

        public LinkedList() {

        }

        public LinkedList(K[] array) {
            head = new Node(array[0], null);

            Node<K> currentPointer = head;
            for(int i = 1; i < array.length; i++) {
                currentPointer.setNext(new Node(array[i], null));
                currentPointer = currentPointer.next();
            }
            tail = currentPointer;
        }

        public void add(K element) {
            if(head == null) {
                head = new Node(element, null);
                tail = head;
            } else {
                tail.setNext(new Node(element, null));
                tail = tail.next();
            }
        }

        public Iterator<Node<K>> iterator() {
            return new Itr(head);
        }

        @Override
        public String toString() {
            StringBuffer str = new StringBuffer();
            Iterator<Node<K>> itr = iterator();
            while(itr.hasNext()) {
                Node<K> current = itr.next();
                str.append(current.getValue().toString());
                str.append("->");
            }
            return str.toString();
        }

        private class Itr implements Iterator<Node<K>> {
            private Node<K> cursor;

            public Itr(Node<K> start) {
                cursor = start;
            }

            @Override
            public boolean hasNext() {
                return cursor !=null;
            }

            @Override
            public Node<K> next() {
                Node<K> currentElement = cursor;
                cursor = cursor.next();
                return currentElement;
            }

            @Override
            public void remove() {
                throw new RuntimeException("Unsupported Operation");
            }
        }

    }

    private class Node<K extends Comparable> {
        K data;
        Node next;

        public Node( K data, Node next) {
            this.data = data;
            this.next = next;
        }

        public void setNext(Node node) {
            next = node;
        }

        public Node<K> next() {
            return next;
        }

        public K getValue() {
            return data;
        }
    }

    public static void main(String args[]) {
        LinkedListMerge llm = new LinkedListMerge();
        llm.mergeLists();
        System.out.println(llm.getMergedList().toString());

    }
}

Answer 1

Simplifying the implementation

That's a lot of code for something that could be done simpler.

Consider this alternative implementation:

• Given the head nodes of two lists
• While both heads are non-null
  • Compare the heads
  • Append to the result the node with the smaller value
  • Advance the head with the smaller value
• Append to the result the head that's non-null

If there are more than 2 lists to merge, apply the algorithm pairwise, repeatedly until 1 final list remains containing all the lists merged.

In code:

Node<K> MergeLists(Node<K> headA, Node<K> headB) {
    Node<K> dummy = new Node<>();
    Node<K> node = dummy;
    while (headA != null && headB != null) {
        if (headA.compareTo(headB) <= 0) {
            node.next = headA;
            headA = headA.next;
        } else {
            node.next = headB;
            headB = headB.next;
        }
        node = node.next;
    }
    if (headA != null) {
        node.next = headA;
    } else {
        node.next = headB;
    }
    return dummy.next;
}

Note that this implementation doesn't create a new list of nodes, but it rewrites the links to form a new linked list. It can be modified to create a new list if necessary.

Organize code for testability

The test data doesn't belong in the constructor of LinkedListMerge. It makes it hard to test the code. It would be better to create an easy entry point for testing, for example a method that takes 2 (or more) lists to merge as parameters.