c++ - 编织链表元素的转轮技术

Question

我一直在阅读《破解编码面试》这本书。我对实现用于编织链表元素的运行者技术有点困惑。本书内容如下:

“假设你有一个链表 a1->a2....->an->b1->b2....bn，并且你想将其重新排列为 a1->b1->a2->b2 ->.....an->bn.你不知道链表的长度，但你只知道它是一个偶数。

对于 p2 的每一次移动，您可以让一个指针 p1(快速指针)每两个元素移动一次。当p1到达链表末尾时，p2将到达端点。然后，将 p1 移回到前面并开始“编织”元素。在每次迭代中，p2 选择一个元素并将其插入到 p1 之后。”

现在我已经了解了编织开始之前的技术。所以，在编织之前，我们基本上有(对于 n=4 个元素)

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

现在，如果我理解正确的话，我必须移动 p2 指向的元素(即 b1)并将其插入到 p1 之后，换句话说

p1.next = p2

这将产生以下列表(？)

a1->b1->b2

算法如何从这里继续进行？

我找到了this问题，但似乎表明上述步骤会导致

a1->b1->a2->b2

我不明白这是怎么回事。我可能在这里遗漏了一些基本的东西。

Answer 1

如果 A1 -> A2 -> ... -> AN -> B1 -> B2 ... -> BN 是你的原始链表，那么在第一步之后你将有 P1 和 P2 分别指向 A1 和 B1。假设 AN 指向 null，这可以在第一步中轻松完成。

在每次迭代时，执行以下步骤:

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

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

P1 = temp1 
P2 = temp2 //4

以下是第一次迭代中四个位置的变化:

1:

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

4:

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

然后重复相同的操作，直到 P1 到达 AN。