リンクされたリストの要素を製織するためのランナーテクニック

Question

私はコーディングインタビューブックを解読しています。私は、リンクされたリストの要素を織り込むためのランナー技法の実装にちょっと固執しています。この本は次のようになります：

"リンクリストa1-> a2 ....-> b1-> b2 .... bnがあり、それをa1-> b1 - > a2 - > b2 - > ..... an - > bnリンクリストの長さは分かりませんが、偶数であることがわかります。

ポインタp1（高速ポインタ）は、p2が作成する1つの移動ごとに2つの要素ごとに移動します.p1がリンクリストの終わりに達すると、p2が終点になります。各繰り返しで、p2が要素を選択し、p1の後に挿入します。

私は織り始める前の技術を理解しています。だから、右織りの前に、私たちは基本的に私が正しく理解していれば

p1  p2 
a1->a2->b1->b2 

は今、私はP2で指さに（すなわちb1）を要素を移動し、P1の後にそれを挿入する必要があります（N = 4つの要素のため）持っています、つまり

p1.next = p2 

次のリストにつながる（？）

a1->b1->b2 

にどのようなアルゴリズムは、ここから進むのでしょうか？

私はthis質問を見つけたが、上記のステップは、私がどのように表示されていない

a1->b1->a2->b2 

につながることを示唆しているようです。おそらく私はここで何か基本的なものを見逃しているでしょう

Answer 1

A1 -> A2 -> ... -> AN -> B1 -> B2 ... -> BNがあなたの元にリンクされたリストである場合は、最初のステップの後に、あなたは、それぞれA1とB1でP1とP2ポインティングを持っています。 ANがnullを指しているとしましょう。これは、最初の手順で簡単に行うことができます。各反復において

、手順ない：

1：

temp1 = P1.next 
temp2 = P2.next //1 

P2.next = P1.next //2 
P1.next = P2 //3 

P1 = temp1 
P2 = temp2 //4 

ここでは、最初の反復の4つの位置での変化である

P1     P2 
⬍     ⬍ 
A1 → A2 → ... → AN B1 → B2 ... → BN 
    ⬍     ⬍ 
    temp1    temp2 

2：

P1 .–––––––––––––––. 
⬍ ↓    ↑ 
A1 → A2 → ... → AN B1 B2 ... → BN 
    ⬍    ⬍ ⬍ 
    temp1   P2 temp2 

3：

P1 .–––––––––––––––. 
⬍ ↓    ↑ 
A1 A2 → ... → AN B1 B2 ... → BN //P2 points on B1 
↓ ⬍    ↑ ⬍ 
↓ temp1   ↑ temp2 
·––––––––––––––––––––· 

これは同等です：

  P1    P2 
      ⬍    ⬍ 
A1 → B1 → A2 → ... → AN B2 ... → BN 
      ⬍    ⬍ 
     temp1   temp2 

そしてP1がANに到達するまで、あなたは同じことを繰り返します。

P1     P2 
⬍     ⬍ 
A1 → B1 → A2 → ... → AN B2 ... → BN 
      ⬍    ⬍ 
     temp1   temp2 

4。

Answer 2

Adam Stelmaszczyk、Igor Tandetnikおよびfour_linesが提示するアルゴリズムは正しいです。終了条件に注意を払わなければならない場合は、リストを終了する最後のnullptrが失われる可能性があります。 four_linesは、製織する前にこれを扱う主張をしています。または、製織中に以下をチェックすることによって行うことができます。

#include "stdafx.h" 
#include <iostream> 

namespace 
{ 
    struct elem 
    { 
     int val; 
     elem* next; 
     elem() : val(-1), next(nullptr) {} 
    }; 
} 

int main() 
{ 
    // setup single-linked list of elements (an array here makes it easy...) 
    const int SIZE = 12; // even number 
    elem elems[SIZE]; 
    for (int x = 0; x < SIZE - 1; ++x) { elems[x].next = &elems[x + 1]; } 
    for (int x = 0; x < SIZE; ++x) { elems[x].val = x; } 

    // divide the list using ptrs pf, ps to point at first part, second part 
    elem* pf = elems; 
    elem* ps = elems; 
    do 
    { 
     pf = pf->next; 
     pf = pf->next; 
     ps = ps->next; 
    } while (pf != nullptr); 
    pf = elems; // move pf back to start 

    // weave first and second parts of list using pf and ps 
    do 
    { 
     // update pf element next-ptr to point at ps, then move pf to its original next element 
     elem* oldpfnext = pf->next; 
     pf->next = ps; 
     pf = oldpfnext; 
     // if ps element is not at end, update ps element next-ptr to point the new location of pf 
     elem* oldpsnext = ps->next; 
     if (nullptr != ps->next) 
     { 
      ps->next = pf; 
     } 
     // now move ps to its original next element (even if null)... 
     ps = oldpsnext; 
    } while (nullptr != ps); // ... and stop if we are now at end 

    return 0; 
}