我一直在阅读《破解编码面试书》。对于链接列表的编织元素，我有点困扰着跑步者技术。这本书如下：
"假设您有一个链接列表a1-> a2 ....-> an-> an-> b1-> b2 .... bn，您想将其重新排列到a1-> b1-> a2-> b2中 -> ..... an-> bn。您不知道链接列表的长度，但您只知道它是一个偶数。
您可以让一个指针P1(快速指针(移动P2所做的每两个元素。当P1击中链接列表的末端时，P2将位于端点。然后，将P1移至前面，然后开始"编织"元素。在每次迭代中，P2选择一个元素并在P1之后插入。"
现在，我了解到编织开始之前的技术。因此，就在编织之前，我们基本上有(n = 4个元素(
p1 p2
a1->a2->b1->b2
现在，如果我正确理解，我必须将元素移动到P2(即B1(并在P1之后插入它，换句话说
p1.next = p2
哪个将导致以下列表(？(
a1->b1->b2
算法如何从这里进行？
我找到了这个问题，但似乎表明上述步骤将导致
a1->b1->a2->b2
我看不到如何。我可能在这里缺少一些基本的东西。
如果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。
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;
}