我正在尝试使用分而治之算法来混合链表,该算法随后在线性(n log n)时间和对数(log n)额外空间中随机混洗链表.
我知道我可以做一个类似于可以在一个简单的数组中使用的Knuth shuffle,但是我不知道如何用分而治之的方式做到这一点.我的意思是,我实际上分裂了什么？我只是划分到列表中的每个单独节点,然后使用一些随机值将列表随机组合在一起？
或者我给每个节点一个随机数,然后根据随机数在节点上进行合并？
algorithm shuffle linked-list divide-and-conquer
algorithm ×1
divide-and-conquer ×1
linked-list ×1
shuffle ×1