Randomly merging two linked lists

Question

I'll start by saying I've looked for and tried several different solutions without luck. I've been working on this for far too long, so any help would be greatly appreciated.

The assignment is to shuffle a linked list representing a deck of cards. I was given all method declarations and was told I'm only allowed to use recursion. I've gone about this in every possible way I can think of without any luck.

Basically the strategy we were told to use is to split the linked list in 2, shuffle both lists (by recursively calling the shuffle method), then merge the shuffled lists back together.

Some stuff you may need to know:

• LLN = Linked List Node
• len = the length of the "this" list
• b = the list to merge "this" with
• blen = the length of the "b" list

This code returns an empty list, and I can't see why (obviously). LLN->shuffle() should return the head of the shuffled list. Right now it's returning an empty list.

LLN * LLN::merge(int len, LLN *b, int blen) {
    //cout << "len: " << len << ", blen: " << blen << endl;

    if (len == 0) return b;
    if (blen == 0) return this;

    int r = rand() % (len + blen) + 1; // between 1 and (len + blen)

    if (r <= len) {
        if (next)
            next = next->merge(len - 1, b, blen);
        else
            next = b;

        return this;
    } else {
        if (b->getnext())
            b->setnext(b->getnext()->merge(blen - 1, this, len));
        else
            b->setnext(this);

        return b;
    }
}

LLN *LLN::shuffle(int len) {
    if (len == 1)
        return this;

    LLN *tmp = split();

    int thisLength = (len + 1) / 2; // for an odd numbered length, "this" list is 1 node larger
    int tmpLength = len / 2;

    shuffle(thisLength);
    tmp = tmp->shuffle(tmpLength);

    return merge(thisLength, tmp, tmpLength);
}

This is how the method is invoked.

void LL::shuffle() {
    if (head != NULL)
        head = head->shuffle(size);
}

The LL (Linked List) object is initialized with the standard 52 cards (each card being a node).

If you need anything else, please let me know.

Thanks very much!

Answer 1

I was able to figure out the problem with help from my prof. Turns out my error was in the base case for my split() method. With that fixed everything works fine. I also applied Charlie's suggestion.

Answer 2

shuffle(thisLength);
tmp = tmp->shuffle(tmpLength);

return merge(thisLength, tmp, tmpLength);

Here shuffle(thisLength)'s return value may not is this, so we should do like this

first = shuffle(thisLength);
tmp = tmp->shuffle(tmpLength);

return first->merge(thisLength, tmp, tmpLength);