I am trying to come up with an algorithm to merge two linked lists. Basically I am trying to combine the lists like below, S = [1, 9, 5, 3] and Q = [0, 4, 3, 6, 6, 2] and result should be [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();
    }
}

It would be great if someone can suggest an algorithm to achieve this.

public static IntList merge(IntList S, IntList Q) {
    //body
}

This is what I have done so far.

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

CodePudding user response：

Your attempt was going in the right direction, but in the recursive step, don't only take the first value from the first list, also take the first value from the second list, and call a recursive merge on both "rests" of the lists.

So change this line:

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

to:

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