我正在尝试提出一种算法来合并两个链表。基本上我试图组合如下列表,S = [1, 9, 5, 3] 和 Q = [0, 4, 3, 6, 6, 2] 结果应该是 [1, 0, 4, 9 , 5, 3, 6, 3,6, 2]
import java.util.Formatter;
public class IntList {
public int first;
public IntList rest;
public IntList(int first0, IntList rest0) {
first = first0;
rest = rest0;
}
public IntList() {
this(0, null);
}
@Override
public int hashCode() {
return first;
}
public static IntList of(Integer... args) {
IntList result, p;
if (args.length > 0) {
result = new IntList(args[0], null);
} else {
return null;
}
int k;
for (k = 1, p = result; k < args.length; k += 1, p = p.rest) {
p.rest = new IntList(args[k], null);
}
return result;
}
public boolean equals(Object x) {
if (!(x instanceof IntList)) {
return false;
}
IntList L = (IntList) x;
IntList p;
for (p = this; p != null && L != null; p = p.rest, L = L.rest) {
if (p.first != L.first) {
return false;
}
}
if (p != null || L != null) {
return false;
}
return true;
}
private int detectCycles(IntList A) {
IntList tortoise = A;
IntList hare = A;
if (A == null) {
return 0;
}
int cnt = 0;
while (true) {
cnt++;
if (hare.rest != null) {
hare = hare.rest.rest;
} else {
return 0;
}
tortoise = tortoise.rest;
if (tortoise == null || hare == null) {
return 0;
}
if (hare == tortoise) {
return cnt;
}
}
}
@Override
public String toString() {
Formatter out = new Formatter();
String sep;
sep = "(";
int cycleLocation = detectCycles(this);
int cnt = 0;
for (IntList p = this; p != null; p = p.rest) {
out.format("%s%d", sep, p.first);
sep = ", ";
cnt++;
if ((cnt > cycleLocation) && (cycleLocation > 0)) {
out.format("... (cycle exists) ...");
break;
}
}
out.format(")");
return out.toString();
}
}
如果有人可以提出一种算法来实现这一点,那就太好了。
public static IntList merge(IntList S, IntList Q) {
//body
}
这是我迄今为止所做的。
public static IntList merge(IntList S, IntList Q) {
if (S == null) {
return Q;
} else if (Q == null) {
return S;
} else {
return new IntList(S.first, merge(Q.rest, S));
}
}
您的尝试朝着正确的方向前进,但在递归步骤中,不仅要从第一个列表中获取第一个值,还要从第二个列表中获取第一个值,并在两个“其余部分”上调用递归合并列表。
所以改变这一行:
return new IntList(S.first, merge(Q.rest, S));
到:
return new IntList(S.first, new IntList(Q.first, merge(Q.rest, S.rest)));
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句