0

最近看了破解代码，第2章介绍了解决多数链表问题的runner方法。

给定链表 a1 a2...an b1 b2...bn 重新排列为 a1 b1 a2 b2...an bn。

它说我们应该使用两个跑步者，速度快的应该是慢速的两倍。

因为总数是偶数，所以越快跑到最后，越慢的在链表中间。然后将较快的跑步者放在链表的开头，并在较快的跑步者之后插入较慢者指向的元素。

我知道这个原则，但我的问题是：

例如

1 2 3 4 1 2 3 4

起初，两个跑步者都指向“1”，

那么跑得快的人指向“3”，跑得慢的人指向“2”。

较快的 funner 指向第二个“1”，较慢的指向“3”。

跑得快的人指向第二个“3”，跑得慢的人指向“4”。

接着 ？我应该怎么办？我不能把快跑者放在第一个“1”，因为我还没有到达链表的末尾。与较慢的相同，它还没有到达链表的中间。

如果我在链表中​​添加一个头，那么快跑者和慢跑者可以到达中间和终点。我的意思是它看起来像下面这样：

0 1 2 3 4 1 2 3 4；

所以我想知道，如果我想使用 runner 方法来解决这个问题，我应该为快跑者和慢跑者添加索引吗？

4

2 回答 2

1 
# This is a testing function by Pengyu CHEN (cpy.prefers.you[at]gmail.com)
# For answering questions on StackOverflow.com
# COPYLEFT, ALL WRONGS RESERVED.

"""
To rearrange a lst from a_1->a_2->...->a_n->b_1->b_2->...->b_n
to a_1->b_1->...->a_i->b_i->...->a_n->b_n
"""
def linked_list_rearrange(lst):
    # step 1:
    fast = lst.head
    slow = lst.head
    while fast != None:
        fast = fast.next
        fast = fast.next # assuming here it won't generage any errors
        slow = slow.next
    # step 2:
    fast = lst.head
    # now slow is at middle of the list, means b_1
    while slow != None:
        temp = slow.next
        slow.next = fast.next
        fast.next = slow
        fast = slow.next
        slow = temp
    return lst

假设您是一名解释器，并将您的输入列表提供给上述函数。通过遵循它的步骤，您将对我认为的算法有一个清晰的认识。

更新：固定：从 fase 到 fast 的错字。
更新：添加：版权（copyleft）信息。

于 2013-09-10T05:24:44.840 回答
0

以编程方式思考。当它说更快的移动速度是两倍时，这意味着在一次迭代中，它需要一步，然后是另一步。

因此，在 之后the faster runner points to the second "3", the slower points to the "4".，较慢的移动到第二个“1”，而较快的第一个移动到第二个“4”。如果更快指向的节点指向NULL（或者如果它是列表中的最后一个节点），则需要检查更快的移动，从而更快地移动到列表中的第一个节点。

然后，只需将当前速度较慢的节点（第二个“1”）移动到当前速度较快的节点（第一个“1”）之后。

高温高压

于 2013-09-10T05:24:19.000 回答