c++ - ポインターを使用した単一リンク リストの並べ替え

Question

キーではなくポインターのみを操作して、バブルソートを使用して単一リンクリストをソートしようとしています。

以下は for ループでスタックし、無限ループします。これがなぜなのかわかりません。リストの最後が見つからない理由を誰か説明してもらえますか?

Node* sort_list(Node* head)
{
    Node * temp;
    Node * curr;
    for(bool didSwap = true; didSwap; ) {
            didSwap = false;
            for(curr = head; curr->next != NULL; curr = curr->next) {
                    if(curr->key > curr->next->key) {
                            temp = curr;
                            curr = curr->next;
                            curr->next = temp;
                            didSwap = true;
                    }
                    cout << curr->next->key << endl;
            }
    }
    return head;

}

キー (データ) がスワップされるようにコードを変更すると、関数は正常に動作しますが、何らかの理由でポインターのみを操作して動作させることができません。

Answer 1

次の問題があります。

3 つのメンバーを含むリストを作成しますptr1->ptr2->ptr3。スワップする前に、次のポインタ セットがあります: curr=ptr1; curr->next=ptr2; curr->next->next=ptr3. スワップを実行すると、 を受け取りますcurr=ptr2; curr->next=ptr1; curr->next->next=ptr2。

たとえば、ptr3 を失いました。次のように内部ループのコードを変更する必要があります。

temp = curr;
temp->next = curr->next->next;    // Save ptr3
curr = curr->next;
curr->next = temp;
didSwap = true;