节点类与链表构造
定义 Node 数据类，手动连接节点构建链表，并编写插入、删除和打印辅助函数，直观展示指针变化。
节点类与链表构造 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是链表
链表是一系列节点，其中每个节点都存储一个值和一个指向下一个节点的指针。与数组不同，节点分散存储在内存中，因此不存在基于索引的 O(1) 访问。作为交换，在任何已知位置插入和删除节点时无需移动元素，操作复杂度为 O(1)。
在 Python 中，我们使用一个包含 val 和 next 的小型类来表示每个节点。将节点彼此连接就形成了链表；最后一个节点的 next 为 None，用于表示链表结束。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')从数组构建链表
在面试中，您经常会得到一个列表，并被要求构造其对应的链表，或者执行相反的转换。辅助函数 build 和 to_list 值得记住：build 会根据数组连接节点，to_list 会遍历链表并收集值，以便进行简单验证。
从 n 个元素构建链表需要 O(n) 的时间和 O(n) 的空间。使用虚拟头节点可以简化第一个节点可能发生变化时的边界情况。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]在头部和 tail 插入
在头部插入新节点的复杂度为 O(1)：创建节点，将它的 next 指向原头节点，并将新节点作为头节点返回。在tail插入则需要遍历到最后一个节点（O(n)），然后连接新节点。
使用虚拟头节点可以消除两种插入操作针对空链表的特殊处理，因为 dummy.next 始终是真正的头节点。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> None按值删除节点
要删除第一个具有给定值的节点，请维护一个位于 curr 前一个位置的 prev 指针。当 curr.val == target 时，设置 prev.next = curr.next，从而跳过该节点。这里使用虚拟头节点尤其有帮助，因为它消除了删除实际头节点时的特殊情况——prev 始终可以从虚拟节点开始。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))可视化指针变化
更新指针时，一个常见错误是丢失对某个节点的跟踪。覆盖指针之前，请始终先保存 next：先执行 saved = curr.next，然后再重新赋值。在编写代码前，将链表画成由箭头连接的方框，并在纸上模拟每次指针更新。这种可视化方法可以避免面试中意外产生空指针错误。
请记住：在 Python 中，重新赋值 curr.next 不会影响 curr 本身；但如果在保存 curr.next 之前丢失了对它的引用，就无法再向前遍历。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4单向链表与双向链表
单向链表只存储一个 next 指针，遍历是单向的。双向链表同时存储 prev 和 next，支持 O(1) 的向后遍历；如果有节点的直接引用，还可以在 O(1) 时间内删除节点，无需使用跟踪 prev 的循环。
Python 的 collections.deque 由双向链表实现，因此支持 O(1) 的 appendleft 和 popleft 操作。在面试中，您通常需要实现单向链表；双向链表则会出现在 LRU 缓存设计中。
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')长度、tail 与打印辅助函数
在任何链表面试中，您都应该准备好以下三个实用函数：length(head) 在 O(n) 时间内统计节点数量，tail(head) 在 O(n) 时间内返回最后一个节点，print_list(head) 则将链表格式化以便调试。提前准备好这些函数后，您就可以专注于核心算法，而不必重新实现辅助逻辑。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)链表中的双指针设置
双指针技巧对于链表和数组同样重要，但这里的指针是链表节点，而不是索引。常见的设置包括用于寻找中点和检测环的慢指针与快指针（快指针的移动速度是慢指针的两倍），以及用于删除和反转的前驱与当前节点组合。
请始终显式初始化两个指针，并仔细处理空值终止检查——当快指针接近末尾时，fast and fast.next 可以避免空指针错误。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)虚拟头节点模式
虚拟头节点（哨兵节点）模式是链表问题中最实用的技巧之一。通过在链表前添加一个值为 0 的虚拟节点，您无需再针对空链表或真实头节点发生变化的情况编写特殊处理。结果始终是 dummy.next。这种模式会出现在合并有序链表、删除倒数第 n 个节点、链表分隔等问题中，也会出现在许多其他问题中。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]时间与空间复杂度
大多数链表操作具有以下复杂度。按索引访问：O(n)——必须从头节点开始遍历。在已知节点处插入或删除：O(1)——只需重新连接指针。在位置 k 处插入或删除：O(k)——需要先进行遍历。搜索：O(n)——最坏情况下需要遍历整个链表。所有原地操作的空间复杂度均为 O(1)（不包括额外数据结构）。
与数组相比，数组支持 O(1) 访问，但由于需要移动元素，插入和删除的复杂度为 O(n)。当经常需要在任意位置插入和删除时，链表更有优势。
链表面试技巧
在编写任何链表代码之前，请用方框和箭头直观地画出链表。请大声确认边界情况：空链表、单节点、长度为偶数和长度为奇数。使用虚拟头节点来简化边界条件。请始终尽早检查 if not head。编写完成后，在一个包含三个节点的链表上跟踪您的解决方案，以便在面试官发现指针错误之前将其找出。
大多数链表错误来自以下三个原因之一：覆盖 next 之前忘记保存它，终止条件存在差一错误，或者没有处理头节点发生变化的边界情况——虚拟节点可以完全消除第三种问题。
快速检查
请测试您对本课数据结构与算法——编码面试准备相关概念的理解。
课程回顾
在本课中，您学到了：链表由节点对象构成，每个节点包含值字段和下一节点字段；虚拟头节点模式可以消除头节点变化的边界情况；以及慢指针与快指针的双指针设置是寻找中点和检测环的基础。接下来我们将学习反转链表，这是最常见的指针问题之一。
常见问题解答
「节点类与链表构造」课时是免费的吗？
是的 — 「节点类与链表构造」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「节点类与链表构造」这节课中我会学到什么？
定义 Node 数据类，手动连接节点构建链表，并编写插入、删除和打印辅助函数，直观展示指针变化。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「节点类与链表构造」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。