algorithm - 重新排列的链表。给定一个链表 a1 a2...an b1 b2...bn 重新排列为 a1 b1 a2 b2...an bn。

Question

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

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

它说我们应该使用两个转轮，快的应该是慢的两倍的速度。

因为总数是偶数，当跑得快的跑到终点时，跑得慢的在链表的中间。然后将较快的跑者放在链表的开头，并将较慢的跑者指向的元素插入到较快的跑者之后。

我知道这个原理，但我的问题是:

例如

1 2 3 4 1 2 3 4

起初，两个运行者都指向“1”，

然后跑得快的指向“3”，跑得慢的指向“2”。

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

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

然后呢？我应该怎么办？我不能把跑得更快的人放到第一个“1”，因为我还没有到达链表的末尾。慢的也是一样，还没到链表的中间。

如果我在链表中​​添加一个头，跑得快的和跑得慢的可以到达中间和末端。我的意思是它将如下所示:

0 1 2 3 4 1 2 3 4;

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

Answer 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) 信息。