随机合并两个链表(Randomly merging two linked lists)

随机合并两个链表(Randomly merging two linked lists)

我首先要说的是我已经寻找并尝试了几种不同的解决方案而没有运气。 我一直在研究这个问题太久了，所以任何帮助都会非常感激。

该任务是洗牌代表一副牌的链表。 我得到了所有的方法声明，并被告知我只允许使用递归。 我已经用尽可能的方式解决了这个问题，没有任何运气。

基本上我们被告知要使用的策略是将链表拆分为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卡（每个卡作为节点）进行初始化。

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

非常感谢！

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!

最满意答案

shuffle(thisLength); tmp = tmp->shuffle(tmpLength); return merge(thisLength, tmp, tmpLength);

这里shuffle（thisLength）的返回值可能不是 这个 ，所以我们应该这样做

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

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.