结合两个相等链表的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 成为快速

设 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 之后。

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

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

采用 p2 并将其移至 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屋！