c++ - リンクリストの変更

Question

単一のリンクリストが与えられますa->b->c->d->1->2->3->4->e->f->g->h->5->6->7->8。このリストをのように変更する必要があります a->1->b->2->c->3->d->4->e->5->f->6->g->7->h->8。

私のアプローチでは、リストから番号を削除して個別に保存する追加のリストを使用します。次に、リストをマージします。誰かがこれを行うためのより良いテクニックを提案できますか？

Answer 1

2つのイテレータがあります。一方（イテレータA）がリストを実行し、数字がヒットすると停止し、もう一方（イテレータB）がリストの先頭に留まるようにします。数字を打ったら、イテレータBのノードの後に​​イテレータAのノードを挿入し、イテレータBを上に移動します。このようにして、別のリストを作成する必要はありません。

編集：Bに挿入した後、イテレータAでアイテムを削除します（キャッチしてくれたTudorに感謝します）。

Answer 2

2つのポインターを取得し、番号を取得するまで2番目のポインターをインクリメントし、番号を取得したらすぐにここからノードを削除して、最初のポインターの後に挿入します。

インタビューの質問なので、インタビュアーは、リストがnull、2つのノード（1-charと1-int）、文字ノードの数、整数ノードの数が異なるなど、すべてのコーナーケースをどのように処理しているかを調べている可能性があります。ブロックなど。