Most efficient way to merge to two sorted Java Linked List (Not custom Linked List)

Question

if a method is merging two sorted Lists, and signature looks like below, someone can pass in a Linked List, and if you use a.get(index), the total runtime complexity will be O(N^2). So seems like Iterators are the only way to go to get O(N) runtime. But it makes the code a bit clunky. Is there any way to simplify this code while maintaining O(N) runtime? Thanks for your help!

 public static List<Integer> mergeListEfficient(List<Integer> a, List<Integer> b) {
 List<Integer> result = new ArrayList<>();
 Iterator<Integer> firstItr = a.iterator();
 Iterator<Integer> secondItr = b.iterator();
 Integer firstVal = firstItr.hasNext() ? firstItr.next() : null;
 Integer secondVal = secondItr.hasNext() ? secondItr.next() : null;
 while (firstVal != null || secondVal != null) {
 if (firstVal != null && secondVal != null) {
 if (firstVal < secondVal) {
 result.add(firstVal);
 firstVal = firstItr.hasNext() ? firstItr.next() : null;
 } else {
 result.add(secondVal);
 secondVal = secondItr.hasNext() ? secondItr.next() : null;
 }
 } else if (firstVal != null) {
 result.add(firstVal);
 firstVal = firstItr.hasNext() ? firstItr.next() : null;
 } else {
 result.add(secondVal);
 secondVal = secondItr.hasNext() ? secondItr.next() : null;
 }
 }
 return result;
}
public static void main(String args[]) throws InterruptedException {
 List<Integer> a = new java.util.LinkedList<>();
 a.add(2);
 a.add(3);
 a.add(5);
 List<Integer> b = new java.util.LinkedList<>();
 b.add(3);
 b.add(5);
 b.add(6);
 System.out.println(mergeListEfficient(a, b));
 //prints correctly [2, 3, 3, 5, 5, 6]
}

• Kartik: return Stream.concat(a.stream(), b.stream()).sorted().collect(Collectors.toList());
• Rex Aex: Hi there, this is an interview question, so I don't think you can use the Stream framework. Think of this like, merge two sorted arrays.

Answer 1

I suggest to introduce new class with interface that better suite for this task.

public class App {
 public static List<Integer> mergeListEfficient(List<Integer> a, List<Integer> b) {
 List<Integer> result = new ArrayList<>();
 BetterIterator firstItr = new BetterIterator(a.iterator());
 BetterIterator secondItr = new BetterIterator(b.iterator());
 while (firstItr.hasValue() && secondItr.hasValue()) {
 Integer firstVal = firstItr.getValue();
 Integer secondVal = secondItr.getValue();
 if (firstVal < secondVal) {
 result.add(firstVal);
 firstItr.move();
 } else {
 result.add(secondVal);
 secondItr.move();
 }
 }
 for(;firstItr.hasValue();firstItr.move()){
 result.add(firstItr.getValue());
 }
 for(;secondItr.hasValue();secondItr.move()){
 result.add(secondItr.getValue());
 }
 return result;
 }
 private static class BetterIterator {
 private final Iterator<Integer> iterator;
 private boolean hasNext;
 private Integer value;
 public BetterIterator(Iterator<Integer> iterator) {
 this.iterator = iterator;
 move();
 }
 public boolean hasValue() {
 return hasNext;
 }
 public Integer getValue() {
 return value;
 }
 public void move() {
 hasNext = iterator.hasNext();
 if (hasNext) {
 value = iterator.next();
 }
 }
 }
 public static void main(String args[]) {
 List<Integer> a = new java.util.LinkedList<>();
 a.add(2);
 a.add(3);
 a.add(5);
 List<Integer> b = new java.util.LinkedList<>();
 b.add(3);
 b.add(5);
 b.add(6);
 System.out.println(mergeListEfficient(a, b));
 //prints correctly [2, 3, 3, 5, 5, 6]
 }
}

PS: In case you allowed to modify your input you can simplify this code.

You can get rid of BetterIterator:

• BetterIterator.hasValue become !a.isEmpty()
• BetterIterator.getValue become a.get(0)
• BetterIterator.move become a.remove(0)