哑节点

本节目标：理解“哑节点”的核心思路，并能把它用于实际开发或面试表达。 哑节点（Dummy Node）或哨兵节点，是在数据结构中使用的一个技巧，特别是在链表操作中。它是一个没有实际数据含义的额外节点，通常作为链表的头部节点（头节点之前）使用。使用哑节点的主要目的是为了简化边界条件的处理，使得链表的插入、删除等操作更加统一和简洁，避免了对空链表和非空链表进行不同处理的需要。

在链表操作中，如果不使用哑节点，那么在进行节点插入、删除时，我们通常需要单独处理位于链表头部的情况，因为头部节点没有前驱节点。这意味着我们需要编写额外的条件语句来处理头部节点的特殊情况，这不仅增加了代码的复杂性，也增加了出错的概率。

使用哑节点后，头部节点之前就有了一个前驱节点（即哑节点），这样对链表的操作就可以统一处理了，包括头部节点的操作也不再是特殊情况。例如，在链表头部插入一个新节点时，我们只需要将新节点插入到哑节点之后，不需要额外判断链表是否为空；同样，在删除头部节点时，我们可以直接操作而不用担心链表为空的情况。

下面是一个使用哑节点的链表构建示例：

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

# 创建一个哑节点作为链表的起始节点
dummy = ListNode()
# cur指针用于遍历链表，初始时指向哑节点
cur = dummy

# 假设我们要将一系列值插入链表
values = [1, 2, 3, 4]
for val in values:
cur.next = ListNode(val)
cur = cur.next

# 现在链表为哑节点 -> 1 -> 2 -> 3 -> 4
# 我们通常返回dummy.next作为链表的头部节点
head = dummy.next

在这个例子中，哑节点dummy使得链表的操作更加简洁，我们不需要检查链表是否为空或者特殊处理链表的头部节点。