3.1 单链表结构定义与节点操作

单链表是链表中最基础的数据结构，它由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。在Python中，我们通常用类来定义节点结构。

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        # val存储节点数据，默认为0
        self.val = val
        # next指向下一个节点，默认为None
        self.next = next

创建链表的基本操作包括：创建新节点、连接节点、遍历链表。

# 创建独立的节点
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)

# 连接节点形成链表
node1.next = node2
node2.next = node3

# 遍历链表并打印值
current = node1
while current is not None:
    print(current.val)  # 打印当前节点的值
    current = current.next  # 移动到下一个节点

实例方法表格

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
创建节点	ListNode(val, next)	创建新节点，val为必需参数（节点值），next为可选参数（默认None）
遍历链表	while current: ...	从头节点开始逐个访问，注意判断current是否为None避免空指针异常
获取长度	get_length(head)	需要传入头节点，返回链表长度，时间复杂度O(n)

完整的链表长度获取示例：

def get_length(head):
    """
    获取链表长度
    参数: head - 链表头节点
    返回: int - 链表长度
    """
    try:
        length = 0
        current = head
        # 遍历链表直到末尾
        while current is not None:
            length += 1
            current = current.next
        return length
    except Exception as e:
        print(f"获取链表长度时发生错误: {e}")
        return 0

# 测试示例
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
print(f"链表长度: {get_length(head)}")  # 输出: 3

这节主要讲解了单链表的基本结构定义和节点操作，包括如何创建节点、连接节点以及遍历链表，这些都是后续链表操作的基础。

3.2 虚拟头节点简化边界处理

在处理链表问题时，经常会遇到需要在头部插入或删除节点的情况，这时候边界条件处理会比较麻烦。虚拟头节点（也叫哨兵节点）就是为了解决这个问题而引入的技巧。

虚拟头节点是一个不存储实际数据的节点，它的next指针指向原链表的头节点。这样无论原链表是否为空，我们都有一个固定的"头"可以操作。

# 不使用虚拟头节点的删除操作（复杂）
def delete_node_without_dummy(head, val):
    """删除值为val的第一个节点（不使用虚拟头节点）"""
    # 特殊情况：要删除的是头节点
    if head is None:
        return None
    if head.val == val:
        return head.next
    
    # 一般情况：删除中间或尾部节点
    current = head
    while current.next is not None:
        if current.next.val == val:
            current.next = current.next.next
            break
        current = current.next
    return head

# 使用虚拟头节点的删除操作（简洁）
def delete_node_with_dummy(head, val):
    """删除值为val的第一个节点（使用虚拟头节点）"""
    # 创建虚拟头节点，指向原头节点
    dummy = ListNode(0)
    dummy.next = head
    
    current = dummy
    # 统一处理所有位置的删除
    while current.next is not None:
        if current.next.val == val:
            current.next = current.next.next
            break
        current = current.next
    
    # 返回真正的头节点
    return dummy.next

实例方法表格

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
创建虚拟头节点	dummy = ListNode(0); dummy.next = head	虚拟节点值通常设为0或-1等无关值，必须将其next指向原头节点
统一边界处理	从dummy开始遍历	所有操作都从虚拟节点开始，避免单独处理头节点的特殊情况
返回真实头节点	return dummy.next	操作完成后必须返回dummy.next作为新的头节点

完整示例：在指定位置插入节点

def insert_at_position(head, pos, val):
    """
    在指定位置插入新节点
    参数: head - 原链表头节点, pos - 插入位置(0-based), val - 插入值
    返回: 新的头节点
    """
    try:
        # 创建虚拟头节点
        dummy = ListNode(-1)
        dummy.next = head
        
        current = dummy
        index = 0
        
        # 找到插入位置的前一个节点
        while current.next is not None and index < pos:
            current = current.next
            index += 1
        
        # 创建新节点并插入
        new_node = ListNode(val)
        new_node.next = current.next
        current.next = new_node
        
        return dummy.next
    except Exception as e:
        print(f"插入节点时发生错误: {e}")
        return head

# 测试示例
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

# 在位置1插入值为5的节点
new_head = insert_at_position(head, 1, 5)
# 结果: 1 -> 5 -> 2 -> 3

虚拟头节点的核心价值在于统一了边界条件的处理，让代码更加简洁和不易出错，特别适用于需要频繁在头部进行操作的场景。

3.3 链表反转：迭代与递归实现

链表反转是面试中的经典问题，有两种主要实现方式：迭代法和递归法。理解这两种方法对掌握链表操作非常重要。

迭代法实现

迭代法通过三个指针来逐步反转链表的方向：

def reverse_list_iterative(head):
    """
    迭代法反转链表
    参数: head - 原链表头节点
    返回: 反转后的头节点
    """
    try:
        prev = None      # 前一个节点，初始为None
        current = head   # 当前节点，从头开始
        
        while current is not None:
            # 保存下一个节点，防止断链
            next_temp = current.next
            # 反转当前节点的指针
            current.next = prev
            # 移动prev和current指针
            prev = current
            current = next_temp
        
        # prev现在指向原链表的最后一个节点，即新头节点
        return prev
    except Exception as e:
        print(f"迭代反转链表时发生错误: {e}")
        return head

递归法实现

递归法的思想是：先反转后面的子链表，再处理当前节点：

def reverse_list_recursive(head):
    """
    递归法反转链表
    参数: head - 原链表头节点
    返回: 反转后的头节点
    """
    try:
        # 基线条件：空链表或只有一个节点
        if head is None or head.next is None:
            return head
        
        # 递归反转后面的子链表
        new_head = reverse_list_recursive(head.next)
        
        # 反转当前连接：head.next现在是子链表的尾节点
        head.next.next = head
        head.next = None
        
        return new_head
    except Exception as e:
        print(f"递归反转链表时发生错误: {e}")
        return head

实例方法表格

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
迭代反转	reverse_list_iterative(head)	时间复杂度O(n)，空间复杂度O(1)，适合长链表
递归反转	reverse_list_recursive(head)	时间复杂度O(n)，空间复杂度O(n)（递归栈），代码简洁但可能栈溢出
边界处理	检查head是否为None	两种方法都需要处理空链表的情况

完整测试示例：

def print_list(head):
    """辅助函数：打印链表"""
    result = []
    current = head
    while current:
        result.append(str(current.val))
        current = current.next
    return " -> ".join(result)

# 创建测试链表: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
current = head
for i in range(2, 6):
    current.next = ListNode(i)
    current = current.next

print("原链表:", print_list(head))

# 测试迭代反转
head_copy1 = ListNode(1)
temp = head_copy1
for i in range(2, 6):
    temp.next = ListNode(i)
    temp = temp.next
reversed_iter = reverse_list_iterative(head_copy1)
print("迭代反转:", print_list(reversed_iter))

# 测试递归反转
head_copy2 = ListNode(1)
temp = head_copy2
for i in range(2, 6):
    temp.next = ListNode(i)
    temp = temp.next
reversed_rec = reverse_list_recursive(head_copy2)
print("递归反转:", print_list(reversed_rec))

链表反转的两种实现各有优劣：迭代法空间效率高，递归法代码更简洁。理解这两种方法有助于掌握指针操作和递归思想，是链表操作的重要基础技能。

3.4 快慢指针应用：判环、找中点、找环入口

快慢指针是链表问题中的重要技巧，通过两个指针以不同速度移动来解决各种问题。最经典的三个应用场景是：判断链表是否有环、找链表中点、找环的入口节点。

判断链表是否有环

def has_cycle(head):
    """
    判断链表是否有环
    参数: head - 链表头节点
    返回: bool - 是否有环
    """
    try:
        if head is None or head.next is None:
            return False
        
        # 快指针每次走两步，慢指针每次走一步
        slow = head
        fast = head
        
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            
            # 如果快慢指针相遇，说明有环
            if slow == fast:
                return True
        
        return False
    except Exception as e:
        print(f"判断环时发生错误: {e}")
        return False

找链表中点

def find_middle(head):
    """
    找链表中点（偶数长度时返回第二个中点）
    参数: head - 链表头节点
    返回: 中点节点
    """
    try:
        if head is None:
            return None
        
        slow = head
        fast = head
        
        # 快指针到达末尾时，慢指针正好在中点
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        
        return slow
    except Exception as e:
        print(f"找中点时发生错误: {e}")
        return None

找环的入口节点

def find_cycle_entry(head):
    """
    找环的入口节点
    参数: head - 链表头节点
    返回: 环的入口节点，无环返回None
    """
    try:
        if head is None or head.next is None:
            return None
        
        # 第一步：判断是否有环，并找到相遇点
        slow = head
        fast = head
        has_cycle_flag = False
        
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                has_cycle_flag = True
                break
        
        if not has_cycle_flag:
            return None
        
        # 第二步：找环入口
        # 一个指针从头开始，另一个从相遇点开始，同步走
        ptr1 = head
        ptr2 = slow
        while ptr1 != ptr2:
            ptr1 = ptr1.next
            ptr2 = ptr2.next
        
        return ptr1
    except Exception as e:
        print(f"找环入口时发生错误: {e}")
        return None

实例方法表格

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
判环	has_cycle(head)	快指针每次走2步，慢指针每次走1步，相遇则有环
找中点	find_middle(head)	偶数长度时返回第二个中点，奇数长度返回唯一中点
找环入口	find_cycle_entry(head)	需要先确认有环，然后用数学原理找入口

完整测试示例：

# 创建无环链表: 1 -> 2 -> 3 -> 4 -> 5
def create_normal_list():
    head = ListNode(1)
    current = head
    for i in range(2, 6):
        current.next = ListNode(i)
        current = current.next
    return head

# 创建有环链表: 1 -> 2 -> 3 -> 4 -> 5 -> 3(环)
def create_cycle_list():
    head = ListNode(1)
    current = head
    nodes = [head]
    for i in range(2, 6):
        current.next = ListNode(i)
        current = current.next
        nodes.append(current)
    # 创建环：最后一个节点指向第3个节点（值为3）
    current.next = nodes[2]
    return head

# 测试判环
normal_list = create_normal_list()
cycle_list = create_cycle_list()

print("无环链表判环:", has_cycle(normal_list))  # False
print("有环链表判环:", has_cycle(cycle_list))   # True

# 测试找中点
normal_list2 = create_normal_list()
middle = find_middle(normal_list2)
print("中点值:", middle.val if middle else None)  # 3

# 测试找环入口
entry = find_cycle_entry(cycle_list)
print("环入口值:", entry.val if entry else None)  # 3

快慢指针技巧的核心在于利用速度差来发现链表的特殊结构。这些应用都基于同一个原理：当快慢指针以2:1的速度移动时，它们的相对位置关系能揭示链表的拓扑结构。掌握这些技巧能高效解决很多链表问题。