交錯2鏈表C++

我有解決方案代碼在這裏：交錯2鏈表C++

// Pre-condition: The fronts of two linked lists are provided. 
// Post-condition: A linked list is returned that is the result of 
// interleaving the elements from each provided list. 
// (e.g. {1, 2, 3} & { 4, 5, 6} would return {1, 4, 2, 5, 3, 6} 

Node* interleave(Node*& front1, Node*& front2) { 
    if(!front1) return front2; 
    if(!front2) return front1; 

    Node* third = front1->next; //this will become the third element 
    Node* fourth = front2->next; // this will be come the fourth element 

    front1->next = front2; 
    front2->next = third; 

    third = interleave(third, fourth); 

    return front1; 
}

我有點明白，但我將永遠無法拿出這樣的事情，因爲我在遞歸很差勁。是否有另一種非遞歸方式來解決這個問題？如果是的話，你能給我一個提示嗎？我試過這個：

Node* interleave(Node*& front1, Node*& front2) { 
    Node* newNode = new Node; 
    while(front1!=NULL && front2!=NULL){ 
     newNode = front1->next; 
     newNode = front2->next; 
     front1 = front1->next; 
     front2 = front2->next; 
    } 
    return newNode; 
}

我敢肯定這是錯誤的，但這是我現在唯一能想出的東西。請幫忙。謝謝

來源

2011-05-25 BPm

這感覺就像一個功課問題。 – Lambdageek 2011-05-25 21:24:40

@Lambdageek：你的觀點？ – 2011-05-26 06:26:23

有代碼中的一些錯誤：

Node* interleave(Node*& front1, Node*& front2)

我沒有看到一個參考的需要一個指針，因爲front1中的第一個元素將繼續保持第一個元素，並且根本不需要與front2混淆。

Node* newNode = new Node; 
while(front1!=NULL && front2!=NULL){ 
    newNode = front1->next;

這是造成內存泄漏 - 你至少分配的sizeof（節點）字節，但隨後你失去的參考指針，你將無法再刪除它。另外，你沒有對newNode做任何事情，所以你也可以把它扔掉。

front1 = front1->next; 
front2 = front2->next;

基本上就是告知FRONT1會頗有點到下一個元素，因爲你通過一個參考FRONT1，你改變了真正的指針。最終，front1或front2將爲NULL，並且循環將終止，所以兩個給定參數中的至少一個將變得無用。你永遠不會改變，所以訂單將保持不變 - 你只是在列表中走。

一種方法可以設置前面2的值front1->旁邊，然後交換指針和迭代再次：

Node *a = front1, *b = front2; 
while (a && b) { 
    Node* tmp = a->next; 
    a->next = b; 
    b = tmp; 
    a = a->next; 
} 
return front1;

我沒有測試這一點，但它應該是接近的工作。如果您使用stl，則可以用std :: swap（）替換冗餘交換代碼。的想法很簡單：假設你有兩個列表：

甲 - >乙 - 「ç - > NULL
d - >電子 - >的F - > NULL

你說A的下一個項目是怎麼回事要在第二個列表中的第一個元素，所以d：

A - > d - >電子 - >的F - > NULL

然後第二列表成爲古代的繼任者，所以只是乙 - > C - > NULL。那您就提前一個指向它的新的未來，或d，那麼你現在有：

d - >電子 - >的F - > NULL
乙 - >ç - > NULL

，你再說一遍：

d - >乙 - 「ç - > NULL
ë - >的F - > NULL

乙 - 」ç - > NULL
的F - > NULL

等等，直到一個NULL是我噸。然後front1，仍然指向A，應該有正確的序列（即，除非我非常錯誤：p）

來源

2011-05-25 21:55:15

我剛剛看到Beta的答案：我同意你應該試着畫出兩個列表 - 這就是我所做的！ – 2011-05-25 21:56:37

whoooaaa，謝謝你的回答！這將幫助我很多 – BPm 2011-05-28 06:50:52

嘗試在一張紙上並行繪製兩個鏈接列表。在節點中放一些數字，只是爲了區分它們。考慮如何重新連接它們以形成一個單一的列表，從頭部（或「前部」）開始，然後逐漸減少。請注意，您必須跟蹤一些特殊節點，例如結果列表的第一個節點和其他幾個節點。模式應該變得清晰。

（請注意，有沒有必要建立一個新的節點與new）

來源

2011-05-25 21:33:39 Beta

Node * newNode = new Node; 你是對的。我前幾天才知道，不應該使用新的建築。謝謝。 – BPm 2011-05-28 06:54:19

交錯2鏈表C++

回答

相關問題