LeetCode 138：为何dictionary.get(node.next)与dictionary[node.next]不等价？

Great question! Let's break down exactly why version 1 works and version 2 fails, and confirm your suspicion about the None node.

The Core Issue: Missing Key for None #

Your dictionary d only maps valid original Node objects to their copied counterparts. It never adds None as a key—because in your first loop, you only iterate over existing nodes (while m: stops when m is None).

When you reach the end of the original list, the last node's next is None. Similarly, any node's random could be None if it doesn't point to another node.

• In version 2, when you do d[n.next] or d[n.random], if n.next/n.random is None, you're trying to access a key that doesn't exist in d. This throws a KeyError and crashes your code.
• In version 1, d.get(n.next) solves this perfectly: the get() method returns None by default if the key isn't found. This is exactly what we want—our copied node's next or random should be None, matching the original node's value.

Let's Test with a Simple Example #

Suppose you have a single node:

Original Node: val=1, next=None, random=None

• Your first loop adds d[original_node] = copied_node to the dict.
• In the second loop (version 2), d[n.next] becomes d[None]—which isn't in the dict, so error.
• In version 1, d.get(n.next) returns None, so copied_node.next = None (correct) and copied_node.random = None (correct).

Code Comparison #

Working Version (Version 1)

"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        d = dict()
        m = head
        while m:
            d[m] = Node(m.val)
            m = m.next
        n = head
        while n:
            d[n].next = d.get(n.next)
            d[n].random = d.get(n.random)
            n = n.next
        return d[head]

Failing Version (Version 2)

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        d = dict()
        m = head
        while m:
            d[m] = Node(m.val)
            m = m.next
        n = head
        while n:
            d[n].next = d[n.next]  # KeyError when n.next is None
            d[n].random = d[n.random]  # KeyError when n.random is None
            n = n.next
        return d[head]

Quick Fix for Version 2 (Optional) #

If you wanted to make version 2 work without get(), you could explicitly add None to your dictionary at the start:

d = {None: None}

This way, accessing d[None] would return None instead of throwing an error. But using get() is cleaner and more idiomatic for this scenario.

内容的提问来源于stack exchange，提问作者Li-Pin Juan