Given a two dimensional linked list, create a flattened sorted list

Question

A node has a next and down pointer. Merge the linked-list such that end result is sorted. Here we have a top level linked-list, followed by a down-list. If { 10 : {20, 30} , 35 { 40, 50 } } is the input data structure. It means that, 10 is connected to 35, using the next pointer. 10 is connected to 20 and 20 to 30 using the down pointer, and 35 is connected to 40 and 40 to 50 using the down pointer. Only the top level list {10 -> 35} use the next pointer, the down level links {10 -> 20 -> 30} and {35 -> 40 -> 50} use the down pointer ONLY. The output should be a list 10 - 20 - 30 - 35 - 40 - 50, and down ptr should be null for all.

This question, like many of my previous questions, is attributed to GeeksForGeeks. Looking for code-review, best practices and optimizations.

Verifying complexity to be O(n), where n is the total nodes in the linked-list.

public class FlattenLinkedList {

    private Node first;
    private Node last;

    public FlattenLinkedList(List<Integer> nodes) {
        for (Integer item : nodes) {
            add(item);
        }
    }


    public FlattenLinkedList(LinkedHashMap<Integer, List<Integer>> nodes) {
        for (Integer item : nodes.keySet()) {
            add(item);
        }

        Node head = first;
        for (List<Integer> items : nodes.values()) {
            addDown(head, items);
            head = head.next; 
        }
    }


    private void add(int item) {
        final Node node = new Node(item);
        if (first == null) {
            first = last = node;
        } else {
            last.next = node;
            last = node;
        }
    }

    private void addDown(Node head, List<Integer> list) {
        Node prev = null;
        for (Integer item : list) {
            Node node = new Node(item);
            if (prev == null) {
                prev = node; 
                head.down = node;
            } else {
                prev.down = node;
            }
            prev = node;
        }
    }


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

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

    public void flatten() {
        Node currNode = first;
        while (currNode != null) {
            merge(currNode);
            currNode = currNode.next;
        }
    }


    private void merge(Node node) {
        Node nodeHorizontal = first;
        Node nodeVertical = node.down;
        node.down = null;

        if (nodeVertical == null) { 
            return; 
        }

        Node prev = null;
        while (nodeHorizontal != null && nodeVertical != null) {
            if (nodeHorizontal.item < nodeVertical.item) {
                if (prev == null) {
                    prev = nodeHorizontal;
                } else {
                    prev.next = nodeHorizontal;
                    prev = prev.next;
                }
                nodeHorizontal = nodeHorizontal.next;
            } else {
                if (prev == null) {
                    prev = nodeVertical;
                } else {
                    prev.next = nodeVertical;
                    prev = prev.next;
                }
                nodeVertical = nodeVertical.next;
            }
        }

        prev.next = nodeHorizontal != null ? nodeHorizontal :  nodeVertical;
    }


    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((first == null) ? 0 : first.hashCode());
        result = prime * result + ((last == null) ? 0 : last.hashCode());
        return result;
    }


    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        FlattenLinkedList other = (FlattenLinkedList) obj;

        Node thisNode = first;
        Node otherNode = other.first;

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

        return thisNode == null && otherNode == null;
    }
}

public class FlattenLinkedListTest {


    @Test
    public void test() {
        LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<Integer,  List<Integer>>();
        map.put(10,  Arrays.asList(20,   30));
        map.put(40,  new ArrayList<Integer>());
        map.put(70,  Arrays.asList(80,   90));
        map.put(100, Arrays.asList(110, 120));

        FlattenLinkedList flat1 = new FlattenLinkedList(map);
        flat1.flatten();

        FlattenLinkedList flat2 = new FlattenLinkedList(new ArrayList<Integer>(Arrays.asList(10, 20, 30, 40, 70, 80, 90, 100, 110, 120)));

        assertTrue(flat1.equals(flat2));
    }


}

Answer 1

Issues I can see in your code (show stoppers):

1. this is a write-only linked list. You can add things in the constructor, but you can never read them out .... what's with that? There is no 'get', or any other mechanism to retrieve data from the list

2. there is no way to add data other than through the constructor

3. The code will fail for the input given like:

   1  ->   2  ->  3  ->  4  ->  5
   L 80    L 70   L 60   L 50   L 40
   L 90    L 75   L 65   L 55   L 45
   

   Note, the requirements stipulate that each list is sorted, not that all the members of successive lists are larger than all members of previous lists.

4. The hashCode method is appalling.... it calcualtes the hashCode on only the first and last nodes (if any), and does nothing with the 'down' or 'inbetween'

5. The equals() method is worse ... it does not work if either list has any down-dimension values.... because it simply ignores that dimension. Since you rely on your equals method to test your implementation, and you don't test your equals method, your tests are useless. In fact, they are worse than useless because they have given you a false sense of correctness, when it's not correct.

Answer 2

Asside @rofl great answer I would also want to give a review and other approach to solve the same problem. The method the most caught my attention for reviewing was the merge method. You have some redundant logic that you may wish to refactor to something like this perhaps:

private void merge(Node node) {
    Node nodeHorizontal = first;
    Node nodeVertical = node.down;
    node.down = null;

    if (nodeVertical == null) { 
        return; 
    }

    Node prev = null;
    Node aux;
    while (nodeHorizontal != null && nodeVertical != null) {
        if (nodeHorizontal.item < nodeVertical.item) {
            aux = nodeHorizontal;
        } else {
            aux = nodeVertical;
        }           
        if (prev == null) {
            prev = aux;
        } else {
            prev.next = aux;
            prev = prev.next;
        }
        aux = aux.next;
    }

    prev.next = aux
}

Lastly, flattening collections is a way to common problem so you may wish to make a generic Component that would flat any Iterable. Something along those lines:

public class FlatIterable<T> implements Iterable<T>{
    private final Iterable<Iterable<T>> iterable;

    public FlatIterable(Iterable<Iterable<T>> iterable){
        this.iterable = iterable;
    }

    public Iterator<T> iterator(){
        final Iterator<Iterable<T>> aux = iterable.iterator();
        if(!aux.hasNext()){
            return new ArrayList<T>().iterator();
        }
        return new Iterator<T>(){
            private Iterator<Iterable<T>> parent = aux;
            private Iterator<T> inner = aux.next().iterator();

            public boolean hasNext(){
                if(inner.hasNext())return true;
                Iterable<T> current = null;
                while(!inner.hasNext()){
                    if(parent.hasNext()){
                        current = parent.next();
                    }else{
                        return false;
                    }
                    inner = current.iterator();
                }
                return true;
            }

            public T next(){
                if(hasNext()){
                    return inner.next();
                }else{
                    throw new NoSuchElementException();
                }
            }

            public void remove(){
                throw new UnsupportedOperationException();
            }
        };
    }
}

Now that is flatten just sort it with quick sort. The easiest way to do that is by copying all items to an ArrayList and then sort that array list. This algorithm is O(n log n)

Answer 3

What you're really asking for is a mergesort, where each of the "down" lists is already sorted and you're trying to merge them into a master list.

Analysis of Computational Complexity

I'm surprised you think this can be done in O(N).

Wikipedia's article on mergesort says:

Merge algorithms generally run in time proportional to the sum of the lengths of the lists; merge algorithms that operate on large numbers of lists at once will multiply the sum of the lengths of the lists by the time to figure out which of the pointers points to the lowest item, which can be accomplished with a heap-based priority queue in O(log n) time, for O(m log n) time, where n is the number of lists being merged and m is the sum of the lengths of the lists.

In other words, if there are a small number of lists you can get O(N) performance, but if there are a large number of lists it takes a nontrivial amount of time to figure out which of the many lists has the smallest element.

(The important factor is how many lists there are compared to the total number of items, not the actual number of lists.)

With many lists the best you can do is O(m log n) time, "where n is the number of lists being merged and m is the sum of the lengths of the lists."

My Solution

The easiest way to solve this in O(N log N) time:

• stick all the elements into a java.util.PriorityQueue.
• Pull them off one at a time.

Pro: easy to implement with reasonable performance.

Con: you could get better performance with a solution that looked only at the top of each list.

Another Solution

If there are a small number of lists you can just compare the top of each list directly. If there are a large number of lists, as Wikipedia says, use a priority queue to quickly find which list has the smallest item in it.