合并到两个排序的Java链表(非自定义链表)的最有效方法

Question

如果一个方法正在合并两个排序的列表，并且签名如下所示，则有人可以传入链表，如果使用.get(index(，则总运行时复杂度将为O(N^2(。看来迭代程序是获得O(N(运行时的唯一途径。但是这使得代码有点笨拙。有没有什么方法可以在维护O(N(运行时的同时简化这些代码？谢谢你的帮助！

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

Answer 1

我建议引入一个新的类，该类的接口更适合此任务。

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:如果您允许修改您的输入，您可以简化此代码。

你可以摆脱BetterIterator:

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