我有一個普通的鏈表：
struct node{
int info;
node* next;
};
我需要撰寫一個遞回函式，它將在 k 個元素之后通過參考傳遞的給定鏈表分成 2 個，將前 k 個節點留在該串列中，并回傳帶有其余節點的第二個串列。
我的迭代解決方案如下所示：
node* split(node*&L, int k){
node* M;
node* head = L;
while(k>1){
head=head->next;
k--;
}
M = head->next;
head->next = NULL;
return M;
}
Output:
L: 1 2 3 4 5 6
after split with: k = 3
L: 1 2 3
M: 4 5 6
這似乎作業得很好。現在我真的想不出一個遞回的解決方案。我正在嘗試：
node* splitL(node*&L, int k){
if(!L) return 0;
if(k<=1){
node* x = L->next;
L->next = NULL;
return x;
}
L->next = splitL(L->next, k-1);
return L;
}
這顯然是錯誤的，因為它將 x 回傳到 L->next 中，因此兩個串列都變為 1 2 3 4 5 6。
我如何為此撰寫遞回函式？引數和回傳型別應該保持不變。此外，如果有人能解釋我如何將我的迭代解決方案轉換為遞回解決方案，那就太好了。
uj5u.com熱心網友回復：
你目前有
node* split(node*&L, int k){
node* M;
node* head = L;
while(k>1){
head=head->next;
k--;
}
M = head->next;
head->next = NULL;
return M;
}
你想要類似的東西
node* split(node*&L, int k){
node* M;
node* head = splitPoint(L, k);
M = head->next;
head->next = NULL;
return M;
}
node* splitPoint(node*&L, int k){
if (k <= 0)
return L;
return splitPoint(L->next, k - 1);
}
注意這個和你原來的守衛都不要k超過串列的長度。
單功能版本：
node* split(node*&L, int k){
if (k <= 0)
{
node* head = L;
node* M = head->next;
head->next = NULL;
return M;
}
return split(L->next, k - 1);
}
uj5u.com熱心網友回復：
起初我沒有看到通過參考傳遞串列指標的意義，但后來我發現它是實作的關鍵。
我認為你可以這樣做：
- 檢查空輸入串列；可能是您被要求將輸入串列拆分到它的末尾 (
k > list size)。 - 檢查
k == 0; 這是進行拆分的重點，因此 1) 回傳當前head節點和 2) 將前一個節點的next指標設定為 null（如果這是第一次呼叫，則設定為串列指標本身）；您這樣做只是將其設定head為 null，因為head它是對您在呼叫中使用的指標的參考split_list。 - 否則，
split_list遞回呼叫。
[演示]
node* split_list(node*& head, int k)
{
if (!head) { return nullptr; }
if (k == 0) { node* ret{head}; head = nullptr; return ret; }
return split_list(head->next, k-1);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/383327.html