随机合并两个链表

首先，我要寻找并尝试了几种不同的解决方案，但都没有碰到运气。我从事此工作已经太久了，因此我们将不胜感激。

分配工作是将代表一副纸牌的链表打乱。我得到了所有方法声明，并被告知只能使用递归。我已经以各种可能的方式解决了这个问题，但没有任何运气。

基本上，我们被告知要使用的策略是将链接列表分为2个，对两个列表进行混洗（通过递归调用shuffle方法），然后将经过混洗的列表合并在一起。

您可能需要了解的一些知识：

• LLN =链表节点
• len =“ this”列表的长度
• b =要合并“ this”的列表
• blen =“ b”列表的长度

这段代码返回一个空列表，我看不出原因（很明显）。LLN-> shuffle（）应该返回随机列表的头部。现在，它正在返回一个空列表。

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

这就是方法的调用方式。

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

LL（链接列表）对象使用标准的52张卡（每张卡是一个节点）初始化。

如果您还有其他需要，请告诉我。

非常感谢！