Leetcode中ListNode的Python逻辑

Question

这里是ListNote类的定义LeetCode：

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

对于代码：

result = ListNode(0)
#result = 0 -> None
result_tail = result
#result_tail = 0 -> None
result_tail.next = ListNode(1)
#result_tail = 0 -> 1 -> None
#result = 0 -> 1 -> None
result_tail = result_tail.next
#result_tail = 1 -> None
#result = 0 -> 1 -> None
result_tail.next = ListNode(2)
#result_tail = 1 -> 2 -> None
#result = 0 -> 1 -> 2 -> None
result_tail = result_tail.next
#result_tail = 2 -> None
#result = 0 -> 1 -> 2 -> None

评论中的值来自我的猜测。我无法理解这一步

result_tail = result_tail.next

result_tail = result是通过引用传递的，所以当result_tail变成 时 1 -> None，result也应该变成1 -> None。为什么result还保留0 -> 1 -> None？而当result_tail变成时1 -> 2 -> None，为什么result将它的尾巴伸向0 -> 1 -> 2 -> None？

result_tail = result_tail.next

就像

result_tail = result.next.next    

谁能告诉我这里的逻辑？

Answer 1

对于那些将来阅读本文的人：我想在本地环境上调试链表问题，所以这就是我所做的。

1. 通过包含 dunder“ repr ”方法修改了 ListNode 的 Leetcode 代码。这适用于当您想要打印 ListNode 以查看其值和下一个节点时。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return "ListNode(val=" + str(self.val) + ", next={" + str(self.next) + "})"

2. 接下来，我创建了一个递归函数，当您传入列表时，该函数会创建一个嵌套的 ListNode。这样您就可以通过传入列表来测试您的方法（而不必自己手动创建一个看起来令人困惑的 ListNode。

def list_to_LL(arr):
    if len(arr) < 1:
        return None

    if len(arr) == 1:
        return ListNode(arr[0])
    return ListNode(arr[0], next=list_to_LL(arr[1:]))

3. 这是一个测试我对“reverseList”问题的答案的示例：

def reverseList(head: ListNode) -> ListNode:
    prev = None
    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node

    return prev


# test cases
t1 = list_to_LL([1, 2, 3, 4, 5])  #ListNode(val=1, next={ListNode(val=2, next={ListNode(val=3, next={ListNode(val=4, next={ListNode(val=5, next={None})})})})})
t2 = list_to_LL([1, 2])  #ListNode(val=1, next={ListNode(val=2, next={None})})
t3 = list_to_LL([])

# answers
print(reverseList(t1))
print(reverseList(t2))
print(reverseList(t3))

Answer 2

对此的简短回答是，Python 是一种传递对象引用语言，而不是问题中暗示的传递引用。这意味着：

1. result并且result_tail 是恰好指向相同值的两个变量
2. 基础值 ( result_tail.next = ListNode(1)) 的变异/更改将影响由result
3. 但是，将变量分配/指向result_tail另一个值不会影响result
4. result_tail = result_tail.next 正在分配当前由变量分配的节点的下一个节点

以下是分配给变量 ( r= result, rt= result_tail)的值的可视化：

result = ListNode(0)
#r
#0 -> None

result_tail = result
#r
#0 -> None
#rt

result_tail.next = ListNode(1)
#r
#0 -> 1 -> None
#rt

result_tail = result_tail.next
#r
#0 -> 1 -> None
#     rt

result_tail.next = ListNode(2)
#r
#0 -> 1 -> 2 -> None
#     rt

result_tail = result_tail.next
#r
#0 -> 1 -> 2 -> None
#          rt

补充阅读参考：

• 一篇详细解释 Python pass-by-object 引用风格的文章https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick/
• 解释 Python 传递对象引用样式的答案/sf/answers/2314660701/
• 关于 Python 的对象引用风格的问题理解 Python 传递函数参数的 call-by-object 风格