Runner技术结合两个相等的链接列表

Question

所以,我在这里面临疑问.

我正在读"Cracking the coding Interview"一书.以下文字写在那里.

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

(这里两个链表长度相同)

对于p2所做的每一次移动,你可以有一个指针p1(快速指针)每两个元素移动一次.当p1命中链表的末尾时,p2将位于端点.然后,将p1移回前面并开始"编织"元素.在每次迭代时,p2选择一个元素并在p1之后插入它.

我不明白当p1到达链表的末尾时,p2将处于中点.如果n = 3(长度= 6),这就是我想象的方式.下面的每个步骤代表一次迭代.

1. a1 (p1, p2)->a2->a3->b1->b2->b3 
2. a1->a2 (p2)->a3 (p1)->b1->b2->b3 
3. a1->a2->a3 (p2)->b1->b2 (p1)->b3 
4. Index out of bounds error because p2 now points to a node after b3.

我错了吗？

Answer 1

我们n = 2.我们从列表开始:

a1 -> a2 -> b1 -> b2

让我们p1成为一个"快速"指针,最初指向头部的后继者.
让我们p2成为一个最初指向头部的"慢"指针.

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

我们移动p1由两个和p2一个直到p1到达列表的末尾(没有下).

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

移动p1回头.

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

进步p2.

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

"编织"开始了.

取元素指向p2并移动它p1.p1插入元素后前进.

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

取元素指向p2并移动它p1.p1插入元素后前进.

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

p1 为null,终止.