组合两个相等链表的 Runner 技术 [英] Runner technique to combine two equal Linked Lists

问题描述

所以，我在这里面临一个疑问.

So, I am facing a doubt here.

我正在阅读《破解编码面试》一书.下面的文字就写在那里.

I was reading the book Cracking the coding Interview. The following text is written over there.

假设你有一个链表a1->a2....->an->b1->b2....bn，你想把它重新排列成a1->b1->a2->b2->.....an->bn.您不知道链表的长度，但您只知道它是偶数.

Suppose you had a linked list a1->a2....->an->b1->b2....bn, and you want to rearrange it into a1->b1->a2->b2->.....an->bn. You don't know the length of the linked list but all you know is that it is an even number.

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

(Here both the linked lists are of same length)

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

You could have one pointer p1 (fast pointer) move every two elements for every one move that p2 makes. When p1 hits the end of the linked list, p2 will be at the endpoint. Then, move p1 back to the front and begin "weaving" the elements. On each iteration, p2 selects an element and inserts it after p1.

我不明白当 p1 到达链表的末尾时，p2 会在中点.如果 n = 3(长度 = 6)，这就是我的想象.下面的每一步都代表一次迭代.

I don't understand how when p1 hits the end of the linked list, p2 will be at the midpoint. This is how I am imagining it if n=3 (length = 6). Each step below represents an iteration.

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.

我是不是走错地方了?

推荐答案

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

Let n = 2. We are starting with a list:

a1 -> a2 -> b1 -> b2

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

Let p1 be a "fast" pointer initially pointing to the successor of head.
Let p2 be a "slow" pointer initially pointing to the head.

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

我们将 p1 移动 2 和 p2 移动 1，直到 p1 到达列表的末尾(没有下一个).

We move p1 by two and p2 by one until p1 reaches the end of the list (there is no next).

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

将 p1 移回头部.

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

提前p2.

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

编织"开始.

将p2指向的元素移到p1之后.插入元素后前进p1.

Take element pointed by p2 and move it after p1. Advance p1 after inserted element.

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

将p2指向的元素移到p1之后.插入元素后前进p1.

Take element pointed by p2 and move it after p1. Advance p1 after inserted element.

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

p1 为空，终止.

这篇关于组合两个相等链表的 Runner 技术的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！