Merge two sorted linked lists in java

merge two sorted linked lists hackerrank
merge two sorted lists python
merge two sorted arraylists java
merge two unsorted linked lists java
merge two sorted arrays
leetcode merge two sorted arrays
merge sort linked list
merge k sorted lists

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

Merge two sorted linked lists, Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4,​  Java Solution. The key to solve the problem is defining a fake head. Then compare the first elements from each list. Add the smaller one to the merged list. Finally, when one of them is empty, simply append it to the merged list, since it is already sorted. public ListNode mergeTwoLists ( ListNode l1, ListNode l2) { ListNode head = new ListNode (0); ListNode p = head; ListNode p1 = l1; ListNode p2 = l2; while( p1 !=null && p2 !=null){ if( p1. val < p2. val){ p. next = p1; p1 = p1. next

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.

Merge two sorted lists (in-place), Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Java. Merge two sorted linked lists Write a SortedMerge() function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. SortedMerge() should return the new list.

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

Merge Two Sorted Lists, Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the​  Trying to figure out what I'm missing in my code that is supposed to merge linked list 2 to the end of linked list 1. Right now it's just getting the last element in the second list and returning that.

LeetCode – Merge Two Sorted Lists (Java), Merge Two Sorted Linked lists solution in Java. Initialize a new LinkedList that represents the merged list ( result ). Now, iterate over both the  The first two are simple. The Print is to help print all the values in the linked list and Push will add value at the tail of the linked list. The Output is 3 5 7 11 As promised since both linked lists are sorted then the expected output is very simple to guess.

Merge two sorted linked lists, Node MergeLists(Node list1, Node list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.data < list2.data) { list1.next  GoodTecher LeetCode Tutorial 21. Merge Two Sorted Lists (Java) http://www.goodtecher.com/leetcode-21-merge-two-sorted-lists-java/ LeetCode Tutorial by GoodTe

Merge Two Sorted Linked Lists, Given two sorted linked lists, merge them so that the resulting linked list is also sorted. Consider two sorted linked lists as an example. widget. The merged linked  Merge Sort for Linked Lists Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. Let head be the first node of the linked list to be sorted and headRef be the pointer to head.

Comments
  • 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 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 :(
  • Please try this approach programcreek.com/2012/12/leetcode-merge-two-sorted-lists-java
  • @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.
  • 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 :)
  • My filaA and filaB are liked lists of data type "long". My IDE says "no suitable method found for addAll(LinkedList)"
  • Sorry, the TreeSet need to be a TreeSet<Long> :) i edited my response
  • Set remove duplicate objects from result. Perhaps this is not required.