Техника бегунов для объединения двух равных списков ссылок

Question

Итак, у меня есть сомнения.

Я читал книгу «Cracking the encoding Interview». Там написано следующее.

Предположим, у вас был связанный список a1->a2....->an->b1->b2....bn, и вы хотите переставить его в a1->b1->a2->b2->.....an->bn. Вы не знаете длину связанного списка, но все, что вы знаете, это четное число.

(Здесь и связанные списки имеют одинаковую длину)

Вы можете иметь один указатель p1 (быстрый указатель) двигаться каждые два элемента для каждого один ход, что p2 делает. Когда 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

Let 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. Advance p1 после вставленного элемента.

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

Примите элемент указываемого p2 и переместить его после p1. Advance p1 после вставленного элемента.

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

p1 - null, завершение.

Answer 2

Начать p2 во втором положении.

a1(p1)-> a2 (p2) -> a3 -> a4 -> b1 -> b2 -> b3 -> b4 
a1-> a2 (p1) -> a3 -> a4 (p2)-> b1 -> b2 -> b3 -> b4 
a1-> a2 -> a3(p1) -> a4 -> b1 -> b2(p2) -> b3 -> b4 
a1-> a2 -> a3 -> a4(p1) -> b1 -> b2 -> b3 -> b4(p2)