链表题类型注解解惑：理解Optional，理解ListNode

反思:: None是Python对“空指针”这一底层概念的高级抽象。（Python的None就是对C语言中“空指针”这个底层操作的高级包装和简化。）
题目（leetcode）网址：203. 移除链表元素 - 力扣（LeetCode）
解答（代码随想录）网址：代码随想录

问题

刚开始刷算法题，移除链表元素这道题，方法的变量定义是def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:我就有些没看懂。
第一个困惑点是不理解Optional[ListNode]的含义，我猜测是head的数据类型为链表节点？但感觉不是很合理，head明明是一个列表。
第二个困惑点是-> Optional[ListNode]这个写到了括号外面，我自己从没这么写过代码，猜测是返回值的类型。

回答

网上查询了一下，记一下2个我猜测对的地方和4个认知盲区。

正确的猜测

（1）ListNode是指的链表节点类型，这是一个自定义数据类型，python中没有。
（2）-> Optional[ListNode]是Python中用于标注函数返回值类型的语法。（因为自己不尝这么写，这次才发现这个标注函数返回值类型是要写在括号外的）

认知盲区

（1）Optional[...]是Python类型注解（Type Hints）的一个高级用法。它来自于 typing 模块。

• Optional[X] 的完整含义是：这个变量的类型可以是 X，也可以是 None。
• 它等价于更长的写法：Union[X, None]。

（2）什么数据类型用Optional[...]来标注？
Optional[X] 的核心语义是：“这里有值（是X类型），或者这里没有值（是None）”。 它代表了一种可能缺失的状态。
具体来说，在数据结构中，指针/引用类型都可以这么标注

• 链表节点：head: Optional[ListNode] （链表可能为空）
• 二叉树节点：left: Optional[TreeNode] （左子节点可能不存在）

（3）从两个角度理解“不存在”
我之前听链表的课，也有不存在这个概念，现在从python这个视角又听到了一次。两次的不存在分别是：

• 1、最后一个节点的指针空间存放的地址为0，代表不存在；
• 2、python中变量的值为None，代表不存在。

这两个角度一个是从c的角度，一个是从python的角度。

从c的角度

1. 指针的本质：就是一个内存地址，通常用一个数字（比如64位的长整数）表示。
2. “空”指针的约定：为了表示“这个指针不指向任何有效的内存地址”，整个计算机行业形成了一个强大的约定：用地址 0（或者0x00000000）来表示“空”（NULL）。
3. 为什么是0？ 因为操作系统会保护低地址的内存（特别是地址0），任何程序试图访问地址0都会引发一个“段错误”或“访问违规”。这完美地帮程序员捕捉到了“使用了未初始化指针”的致命错误。

所以，在C/C++这类接近硬件的语言中，链表的实现就是：

struct ListNode {int val;struct ListNode *next; // ‘next’ 就是一个存储着地址数字的变量
};// 最后一个节点的 next 指针被赋值为 NULL，而 NULL 就是一个宏定义，值是 0
node->next = NULL;

在这个层面，next 里存储的就是一个数字 0。

从python的角度

1. python没有指针：python中的变量像一个“写有内存地址的标签”，更抽象的称呼是“引用”
2. “空”引用的实现：Python需要一种方式来表示“这个引用不指向任何对象”。它选择了一个独一无二的内置对象——None。
3. 为什么是None?
   • 基础共识：None 是一个通用于所有类型的“空”标记。不管是要表示一个空的整数、字符串、列表，还是一个自定义的 ListNode，永远都用同一个 None。
   • 绝对无歧义：None 是Python语言中的一个单例对象（整个程序里只有一个None）。它有自己的类型（NoneType），有自己的内存地址。它存在的唯一目的就是代表“空”或“无”。

所以，在Python中，链表的实现是：

class ListNode:def __init__(self, val=0, next=None): # 这里的next期望接收一个“引用”self.val = valself.next = next   # ‘next’ 是一个变量，里面存储着一个引用# 最后一个节点的 next 引用被赋值为 None 这个特殊对象
node.next = None

在这个层面，next 里存储的是对 None 这个特殊对象的引用。

（4）为什么可以这么注释head: Optional[ListNode]，将head的数据类型注释为链表节点。题目写的head=[1,2,6,3,4,5,6]，这个数据类型不是列表吗？python编译时不会检查变量的数据类型与标注是否相符吗？

首先是，不检查。Python 在运行时不会强制检查类型注解。

其次是，head=[1,2,6,3,4,5,6]只是题目描述。
这并不代表Python代码层面直接给一个列表。LeetCode在幕后做了转换，根据列表创建了一整套 ListNode 对象，并将它们连接起来。类似下面这种操作：

# LeetCode 后台执行了类似这样的代码：
my_list = [1,2,3,4]nodes = [ListNode(val=num) for num in my_list]
for i in range(len(nodes)-1):nodes[i].next = nodes[i+1]
real_head = nodes[0] # 这才是真正传入函数的参数