python - 链表如何更新？

Question

此函数用于合并两个已排序的链表:

def merge(l1, l2):
    head = sort_list = Node(0)
    while l1 and l2:
        if l1.value < l2.value:
            sort_list.next = l1
            l1 = l1.next
            sort_list = sort_list.next
        elif l1.value >= l2.value:
            sort_list.next = l2
            l2 = l2.next
            sort_list = sort_list.next

    sort_list.next = l1 or l2

    return head.next


class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None

所以对于这样的两个列表:

[1,2,4]
[3,4,5]

合并后的结果是:[1,2,3,4,4,5] 调用上面的函数时。

我对代码不理解的是这两行:

sort_list.next = l1
sort_list = sort_list.next

对于第一行，每次更新“sort_list”时都会更新“head”。对于第二行，当更新 sort_list 时，'head' 不受影响。为什么在第二种情况下'head'没有相应改变？在这两种情况下，“head”都是“sort_list”的引用，因此它应该始终随“sort_list”而变化。不对吗？

Answer 1

在最后一段中，您的初始陈述不正确。 head 和 sort_list 作为对 0 节点对象的引用开始。此后，head 仍然指向该节点，而 sort_list 沿着合并列表向下移动。

sort_list = sort_list.next

是增量语句，将sort_list移动到刚刚添加到列表中的节点。 sort_list 不断移动到每个添加的节点，因此它停留在合并列表的末尾。

在底部，函数返回head.next，这是合并列表的顶部节点。

尝试添加一些简单的 print 语句来跟踪执行:

def merge(l1, l2):
    head = sort_list = Node(0)
    while l1 and l2:
        print("\nhead", id(head), head.value)
        if l1.value < l2.value:
            sort_list.next = l1
            l1 = l1.next
            sort_list = sort_list.next
            print("sort_list l1", id(sort_list),
                  sort_list.value if sort_list else None,
                  l1.value if l1 else None)

        elif l1.value >= l2.value:
            sort_list.next = l2
            l2 = l2.next
            sort_list = sort_list.next
            print("sort_list l2", id(sort_list), 
                  sort_list.value if sort_list else None,
                  l2.value if l2 else None)

输出:

head 140689225387368 0
sort_list l1 140689225387144 1 2

head 140689225387368 0
sort_list l1 140689225387088 2 4

head 140689225387368 0
sort_list l2 140689225387312 3 4

head 140689225387368 0
sort_list l2 140689225387256 4 5

head 140689225387368 0
sort_list l1 140689225386976 4 None

看到了吗？ head 保持不动，而 sort_list 沿着建筑物合并移动。