隨機合併兩個鏈表

我會先說我找過並嘗試過幾種不同的解決方案，但沒有運氣。我一直在研究這個太久，所以任何幫助將不勝感激。隨機合併兩個鏈表

該任務是洗牌代表一副牌的鏈接列表。我被給了所有的方法聲明，並被告知我只允許使用遞歸。我已經盡了各種可能的方式去解決這個問題，但沒有任何運氣。

基本上我們被告知要使用的策略是在2中拆分鏈表，通過遞歸調用shuffle方法對兩個列表進行混洗，然後將混洗列表重新合併在一起。

一些東西，你可能需要知道：

LLN =鏈接列表節點
LEN = 「此」名單
B的長度=列表合併「本」與
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張卡（每張卡作爲節點）進行初始化。

如果您需要任何其他信息，請讓我知道。

非常感謝！

來源

2014-02-13 cohenadair

但問題是什麼？舉一個你想要什麼和你得到什麼的例子？ – rendon

我希望它洗牌清單。我得到的是一個空的列表。 LLN-> shuffle（）應該返回混洗列表的頭部（因此爲什麼在LL-> shuffle（）中頭節點被重置）。 – cohenadair

什麼是做'split（）'方法？ – rendon

我能想出的幫助問題從我的教授。原來我的錯誤是在我的split（）方法的基本情況下。隨着固定一切正常。我也申請了查理的建議。

來源

2014-02-13 17:57:49 cohenadair

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

return merge(thisLength, tmp, tmpLength);

這裏洗牌（thisLength）的返回值可能不是這個，所以我們應該做這樣的

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

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

來源

2014-02-13 05:22:04 Charlie

我試過之前（和剛剛做過），它仍然返回一個空列表。 – cohenadair

隨機合併兩個鏈表

回答

相關問題