Merge two sorted linked lists in java

Question

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.

I also tried to move the n = iterA.next();m = iterB.next(); outside the while loop Did you move it above the while loop? — Priyank
– Priyank, Commented Mar 19, 2017 at 17:04
@Priyank yes. Before the while. I didn't work either. Only works if the lists are the same lenght but then one of the elements won't enter the result :( — Lotte
– Lotte, Commented Mar 19, 2017 at 17:06
Please try this approach programcreek.com/2012/12/leetcode-merge-two-sorted-lists-java — Raghu
– Raghu, Commented Mar 19, 2017 at 17:19
@Raghu I have already seen it, but I don't understand it, I have only very basic knowledge. Also, in the comments some people say is wrong. — Lotte
– Lotte, Commented Mar 19, 2017 at 17:25

Pierre · Accepted Answer · 2017-03-19 17:34:12Z

2

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.

edited Mar 19, 2017 at 17:34

answered Mar 19, 2017 at 17:19

Pierre

311 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Lotte Over a year ago

My filaA and filaB are liked lists of data type "long". My IDE says "no suitable method found for addAll(LinkedList)"

Pierre Over a year ago

Sorry, the TreeSet need to be a TreeSet<Long> :) i edited my response

Ilya Over a year ago

Set remove duplicate objects from result. Perhaps this is not required.

Markus · Accepted Answer · 2017-03-19 17:55:23Z

1

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);

edited Mar 19, 2017 at 17:55

answered Mar 19, 2017 at 17:28

Markus

1,1712 gold badges10 silver badges25 bronze badges

1 Comment

Lotte Over a year ago

Thanks so much. It needs a "filafusion.add(m);" right after the first else (same to the other else), otherwise it will not add the last one to filafusion. But this is exactly what I needed and can understand :)

Ilya · Accepted Answer · 2018-10-22 11:02:43Z

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;
}

Collectives™ on Stack Overflow

Merge two sorted linked lists in java

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related