为何链表插入函数未更新root却仍能正常运行？

你的代码 #

def insert(self, root, item):
    # Given the root/head of a Linked List, append the item to the end of the Linked List
    # Function should return the root/head of the Linked List
    if root is None:
        return Node(item)
    else:
        current = root
        while current.next is not None:
            current = current.next
        current.next = Node(item)
        return root

你的疑问 #

我无法理解上述链表插入函数的return语句逻辑。在代码中，我并未对root进行任何更新操作，但返回root后该insert函数却能正常执行。我原本认为这种情况不可行，因为root与初始状态完全相同，恳请您帮我解释其中原理。

核心解释：链表是引用类型，操作的是内存中的对象本身 #

你困惑的根源是没搞清楚Python里引用类型的工作逻辑：

• 当链表不为空时，root是指向链表头节点的引用（相当于指向内存地址的指针）。你确实没修改root这个引用本身，但你修改了root指向的链表结构里的节点。
• 代码里的current是从root复制来的引用，顺着current.next遍历到链表最后一个节点后，给这个节点的next属性赋值为新节点——这一步直接修改了原链表的末尾，把新节点接了上去。
• root作为头节点的引用，它指向的还是原来那个链表的开头，只不过这个链表的长度已经被你修改了。返回root只是把这个头节点的引用返回给调用者，这样调用者就能通过这个引用访问到更新后的完整链表。

两种场景的具体说明 #

• 当链表为空（root is None）时，需要创建新节点作为头节点，所以直接返回这个新节点的引用。
• 当链表不为空时，头节点本身不需要改变，改变的是链表的末尾节点，所以直接返回原来的头节点引用就行——因为它指向的链表已经被修改了。

举个直观例子：
假设原链表是A -> B，root指向A。调用insert(root, C)后，代码会找到B，把B的next改成C，链表变成A -> B -> C。root依然指向A，返回它之后，调用者拿到的还是A，但通过A能遍历到新增的C。

内容的提问来源于stack exchange，提问作者Jangaver 061