合并两个链表

Question

我正在尝试提出一种合并两个链表的算法。基本上我正在尝试组合如下列表， 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));
    }
}

Answer 1

您的尝试方向正确，但在递归步骤中，不仅要从第一个列表中获取第一个值，还要从第二个列表中获取第一个值，并对两者调用递归合并列表的“其余部分”。

所以改变这一行：

return new IntList(S.first, merge(Q.rest, S));

至：

return new IntList(S.first, new IntList(Q.first, merge(Q.rest, S.rest)));

合并两个链表

Merge two linked lists

java

recursion

linked-list

dynamic