CODEWITHSUNDEEP
javasorting
Lotte
Lotte

Reputation: 113

Merge two sorted linked lists in java

I need to merge two sorted linked list into one sorted list. I've been trying to do so for hours, but when I reach the end of one of the list I always have some trouble. This is the best I could do. My filaA and filaB are liked lists of data type "long".

            LinkedList<Long> result= new LinkedList<Long>();
            iterA = filaA.listIterator();
            iterB = filaB.listIterator();
            while (iterA.hasNext() && iterB.hasNext()) {
                n = iterA.next();
                m = iterB.next();
                if (n <= m) {
                    filafusion.add(n);
                    n = iterA.next();
                } else {
                    filafusion.add(m);
                    m = iterB.next();
                }
            }
            if (iterA.hasNext()) {
                while (iterA.hasNext()) {
                    filafusion.add(iterA.next());
                }
            } else {
                while (iterB.hasNext()) {
                    filafusion.add(iterB.next());
                }
            }
            iterfusion = filafusion.listIterator();
            while (iterfusion.hasNext()) {
                System.out.print(iterfusion.next());
            }
        }

The general idea here is to compare one by one and then move the iterator to the next. But they are moving at the same time, so I'm only comparing first with first, second with second, and so on.

I also tried to move the n = iterA.next();m = iterB.next(); before the while loop, which makes it work much better, but then I don't know which list runs out of elements. Only works if the lists are the same lenght but then one of the elements won't enter the result.

I've seen many codes for this here, but they all use Nodes and recursion and stuff I'm not familiar with. I think using iterators will make it more efficient, but that's what's got me so confused, I'm not iterating where I should :(

Any suggestions will be appreciated.

Upvotes: 1

Views: 1955

Answers (3)

Ilya
Ilya

Reputation: 728

public static <T extends Comparable<T>> List<T> mergeSortedLists(List<T> list1, List<T> list2) {
    List<T> result = new ArrayList<>();
    Iterator<T> iterator1 = list1.iterator();
    Iterator<T> iterator2 = list2.iterator();
    boolean hasNext1 = iterator1.hasNext();
    boolean hasNext2 = iterator2.hasNext();
    T next1 = hasNext1 ? iterator1.next() : null;
    T next2 = hasNext2 ? iterator2.next() : null;
    while (hasNext1 || hasNext2) {
        if (!hasNext1) {
            result.add(next2);
            hasNext2 = iterator2.hasNext();
            next2 = hasNext2 ? iterator2.next() : null;
        } else if (!hasNext2) {
            result.add(next1);
            hasNext1 = iterator1.hasNext();
            next1 = hasNext1 ? iterator1.next() : null;
        } else {
            if (next1.compareTo(next2) < 0) {
                result.add(next1);
                hasNext1 = iterator1.hasNext();
                next1 = hasNext1 ? iterator1.next() : null;
            } else {
                result.add(next2);
                hasNext2 = iterator2.hasNext();
                next2 = hasNext2 ? iterator2.next() : null;
            }
        }
    }
    return result;
}

Upvotes: 0

Markus
Markus

Reputation: 1171

I just adapted your code. If you are able to use Java 8, then I have a much shorter solution below. 

    Iterator iterA = filaA.listIterator();
        Iterator iterB = filaB.listIterator();
        Long n = (Long)iterA.next();
        Long m = (Long)iterB.next();
        while (true) {
            if (n <= m) {
                filafusion.add(n);
                if(iterA.hasNext()){
                    n = (Long)iterA.next();
                }
                else{
                    filafusion.add(m);
                    while(iterB.hasNext()){
                        filafusion.add((Long)iterB.next());
                    }
                    break;
                }
            } else {
                filafusion.add(m);
                if(iterB.hasNext()){
                    m = (Long)iterB.next();
                }
                else{
filafusion.add(n);
                    while(iterA.hasNext()){
                        filafusion.add((Long)iterA.next());
                    }
                    break;
                }

            }
        }
        Iterator iterfusion = filafusion.listIterator();
        while (iterfusion.hasNext()) {
            System.out.println(iterfusion.next());
        }

Here is the Java 8 way to do it. And it also works for unsorted input lists:

    Stream stream = Stream.concat(filaA.stream(), filaB.stream());
    stream.sorted().forEach(System.out::println);

Upvotes: 1

Pierre
Pierre

Reputation: 31

You can use the standard java.util.TreeSet to do the job.

here is a full example :

    LinkedList<Long> filaA = new LinkedList<>();
    filaA.add(1l);
    filaA.add(3l);
    filaA.add(5l);
    LinkedList<Long> filaB = new LinkedList<>();
    filaB.add(2l);
    filaB.add(4l);
    filaB.add(6l);

    Set<Long> result = new TreeSet<>();
    result.addAll(filaA);
    result.addAll(filaB);
    System.out.println(result);

TreeSet use natural order.

Upvotes: 2

Related Questions