我正在嘗試從排序的鏈接串列中洗掉重復項。我已經撰寫了演算法，但仍然缺少一個我無法追蹤的核心錯誤邏輯。
考慮串列 1->2->3->3->4->4->5
輸出應該是 1 - > 2 - > 5 程式在簡單情況下作業正常，例如 1>2>2>3，但對于多個重復項，例如 1>2>2>3>3>5，它輸出 1>3> 5 這是一個完整的程式：
struct Node
{
Node* next;
int val;
Node()
{
}
};
int main()
{
Node* n1 = new Node();
n1->val = 1;
Node* n2 = new Node();
n2->val = 2;
n1->next = n2;
Node* n3 = new Node();
n3->val = 3;
n2->next = n3;
Node* n4 = new Node();
n4->val = 3;
n3->next = n4;
Node* n5 = new Node();
n5->val = 4;
n4->next = n5;
Node* n6 = new Node();
n6->val = 4;
n5->next = n6;
Node* n7 = new Node();
n7->val = 5;
n6->next = n7;
n7->next = nullptr;
Node* fast = n1->next;
Node* slow = n1;
Node* temp = n1;
Node* prevSlow = nullptr;
while (slow != nullptr && fast != nullptr)
{
if (fast->val == slow->val)
{
prevSlow->next = fast->next;
fast = fast->next;
slow->next = prevSlow->next;
}
else {
prevSlow = slow;
slow = slow->next;
fast = fast->next;
}
}
}
uj5u.com熱心網友回復：
對于初學者這個建構式
Node()
{
}
沒有意義。去掉它。
該宣告
prevSlow->next = fast->next;
在這個 if 陳述句中
if (fast->val == slow->val)
{
prevSlow->next = fast->next;
fast = fast->next;
slow->next = prevSlow->next;
}
通常可以呼叫未定義的行為，因為最初將指標prevSlow設定為nullptr
Node* prevSlow = nullptr;
注意節點n1是鏈表的頭節點。它可以在洗掉重復項的程序中更改。您還需要釋放已洗掉節點的記憶體。
該演算法可以通過以下方式實作
auto is_duplicate = [] ( const Node *node )
{
return node->next != nullptr && node->val == node->next->val;
};
for ( Node **current = &n1; *current != nullptr; )
{
if ( is_duplicate( *current ) )
{
do
{
Node *tmp = *current;
*current = ( *current )->next;
delete tmp;
} while ( is_duplicate( *current ) );
Node *tmp = *current;
*current = ( *current )->next;
delete tmp;
}
else
{
current = &( *current )->next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400681.html
上一篇：Python無法識別numpy
下一篇：如何生成二進制檔案