拆分链表 Python

Question

我最近开始学习数据结构，我想知道最后3行是怎么回事...

def frontBackSplit(self):
    source = self.root
    # if the length is less than 2, handle it separately
    if source is None or source.next is None:
        return source, None

    slow, fast = source, source.next

    # advance `fast` two nodes, and advance `slow` one node
    while fast:

        fast = fast.next
        if fast:
            slow = slow.next
            fast = fast.next

    # `slow` is before the midpoint of the list, so split it in two
    # at that point.
    ret = source, slow.next
    slow.next = None
    return ret

我理解这个slow/fast策略是寻找中点，但是当:

ret = source, slow.next
slow.next = None
return ret

我不明白这如何允许拆分链表。谁能帮帮我？

Answer 1

当你这样做时：

ret = source, slow.next

这将创建一个包含两项的元组：当前列表的开头和第二个列表的开头。然后你做：

slow.next = None

它通过使 slow 成为第一个列表的末尾来打破链条。因此，当您 return ret 时，您正在 return 第一个列表的开始（现在结束于 slow），以及第二个列表的开始（从 slow).

之后的节点开始

假设我们有

1 -> 2 -> 3 -> 4 -> 5

其中source是1，slow是3。当我们做第一条语句时，ret会指向(1,4).然后我们打破 3 的列表，我们剩下

(  1 -> 2 -> 3   ,   4 -> 5 )

Answer 2

函数开始时，source设置为头节点，self.root:

source
/---\    /---\    /---\    /---\    /---\    /---\
|   | -> |   | -> |   | -> |   | -> |   | -> |   |
\---/    \---/    \---/    \---/    \---/    \---/

迭代将指针 fast 和 slow 向下移动到列表中。当 fast 落在列表末尾时，slow 位于中点。 source 还在原来的地方。

source            slow
/---\    /---\    /---\    /---\    /---\    /---\
|   | -> |   | -> |   | -> |   | -> |   | -> |   |
\---/    \---/    \---/    \---/    \---/    \---/

现在我们做：

ret = source, slow.next

注意 source 仍然指向链表的头部，但是我们在这个点之后不再使用它所以它是无关紧要的；让我们只关注 ret 和 slow:

ret[0]            slow     ret[1]
/---\    /---\    /---\    /---\    /---\    /---\
|   | -> |   | -> |   | -> |   | -> |   | -> |   |
\---/    \---/    \---/    \---/    \---/    \---/

注意ret[0]和ret[1]是我们要return的两个half-lists的头节点，但是这两个还是一个单链表的一部分.要真正拆分列表，我们需要切断slow和ret[1]之间的连接，也就是slow.next指针：

slow.next = None

给我们：

ret[0]                     ret[1]
/---\    /---\    /---\    /---\    /---\    /---\
|   | -> |   | -> |   |    |   | -> |   | -> |   |
\---/    \---/    \---/    \---/    \---/    \---/

现在我们有两个列表，我们 return 为 ret。

拆分链表 Python

Splitting Linked Lists Python

python

linked-list