从‘头歌’实训题到面试真题：用Python链表搞定合并、交集、差集与奇偶分割

从链表基础到面试实战Python实现合并、交集、差集与奇偶分割的进阶指南链表作为数据结构中的基础但重要组成部分在技术面试中占据着举足轻重的地位。无论是校招还是社招链表相关的问题几乎成为必考内容。本文将带你从基础链表操作出发逐步深入探讨合并、交集、差集以及奇偶分割等常见面试题型并提供Python实现的详细解析与优化技巧。1. 链表基础与Python实现在开始解决复杂问题之前我们需要先构建一个可靠的链表基础结构。Python中实现链表通常通过定义节点类和链表类来完成。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class LinkedList: def __init__(self): self.head None def append(self, val): if not self.head: self.head ListNode(val) else: current self.head while current.next: current current.next current.next ListNode(val) def __str__(self): values [] current self.head while current: values.append(str(current.val)) current current.next return -.join(values)关键点解析ListNode类表示链表中的单个节点包含值(val)和指向下一个节点的指针(next)LinkedList类提供基本的链表操作如追加元素(append)__str__方法用于打印链表内容便于调试提示在实际面试中可能需要直接操作节点而不使用完整的链表类。理解节点间的指针关系是解决链表问题的核心。2. 合并两个有序链表合并两个有序链表是面试中最常见的问题之一考察对指针操作和边界条件的处理能力。2.1 迭代解法def mergeTwoLists(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(-1) prev dummy while l1 and l2: if l1.val l2.val: prev.next l1 l1 l1.next else: prev.next l2 l2 l2.next prev prev.next prev.next l1 if l1 else l2 return dummy.next复杂度分析时间复杂度O(nm)其中n和m分别是两个链表的长度空间复杂度O(1)只使用了常数级别的额外空间2.2 递归解法def mergeTwoListsRecursive(l1: ListNode, l2: ListNode) - ListNode: if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next mergeTwoListsRecursive(l1.next, l2) return l1 else: l2.next mergeTwoListsRecursive(l1, l2.next) return l2面试常见变体合并K个有序链表可使用优先队列或分治法合并两个链表后去重合并时交替取节点如第一个链表取一个第二个链表取一个3. 链表交集与差集问题链表交集和差集问题考察对双指针技巧的灵活运用通常要求空间复杂度为O(1)。3.1 链表交集实现def getIntersectionNode(headA: ListNode, headB: ListNode) - ListNode: if not headA or not headB: return None # 计算两个链表的长度 lenA, lenB 0, 0 pA, pB headA, headB while pA: lenA 1 pA pA.next while pB: lenB 1 pB pB.next # 长链表先走差值步 pA, pB headA, headB if lenA lenB: for _ in range(lenA - lenB): pA pA.next else: for _ in range(lenB - lenA): pB pB.next # 同时前进直到找到交点 while pA and pB: if pA pB: return pA pA pA.next pB pB.next return None3.2 链表差集实现def difference(headA: ListNode, headB: ListNode) - ListNode: # 创建哈希集合存储B链表的值 b_values set() current headB while current: b_values.add(current.val) current current.next # 创建虚拟头节点处理删除情况 dummy ListNode(0) dummy.next headA prev, current dummy, headA while current: if current.val in b_values: prev.next current.next else: prev prev.next current current.next return dummy.next优化技巧对于有序链表可以使用双指针法避免使用额外空间处理大型链表时考虑分块处理以减少内存消耗实际面试中可能需要先对链表进行排序再求差集4. 链表奇偶分割奇偶分割问题要求按照节点位置而非值来分割链表考察对链表指针的精确控制。4.1 标准解法def oddEvenList(head: ListNode) - ListNode: if not head: return head odd head even head.next even_head even while even and even.next: odd.next even.next odd odd.next even.next odd.next even even.next odd.next even_head return head执行过程示例原始链表: 1-2-3-4-5-NULL 步骤分解: 1. odd1, even2, even_head2 2. odd.next3 (1-3), odd移动到3 even.next4 (2-4), even移动到4 3. odd.next5 (3-5), odd移动到5 even.nextNULL (4-NULL), even移动到NULL 4. 连接odd和even_head: 5-2 最终结果: 1-3-5-2-4-NULL4.2 变体问题按值奇偶分割根据节点值的奇偶性而非位置分割def oddEvenListByValue(head: ListNode) - ListNode: if not head: return head odd_dummy ListNode(0) even_dummy ListNode(0) odd, even odd_dummy, even_dummy current head while current: if current.val % 2 1: odd.next current odd odd.next else: even.next current even even.next current current.next even.next None odd.next even_dummy.next return odd_dummy.next分组反转每k个节点为一组进行反转交替分割将链表分成两个交替的子链表5. 面试实战技巧与常见问题5.1 调试链表问题的技巧可视化链表在纸上画出链表结构和指针变化边界条件检查空链表输入单节点链表头节点/尾节点特殊情况循环检测使用快慢指针判断链表是否有环def hasCycle(head: ListNode) - bool: if not head or not head.next: return False slow, fast head, head.next while slow ! fast: if not fast or not fast.next: return False slow slow.next fast fast.next.next return True5.2 常见面试问题分类问题类型经典题目考察重点基本操作反转链表、删除节点指针操作双指针环形链表、相交链表快慢指针合并拆分合并K个链表、奇偶分割分治思想数学相关两数相加、回文链表数学思维5.3 性能优化策略空间换时间使用哈希表存储节点信息多指针技巧处理复杂遍历需求递归与迭代转换根据问题特点选择合适方法虚拟头节点简化边界条件处理# 使用虚拟头节点删除指定节点示例 def removeElements(head: ListNode, val: int) - ListNode: dummy ListNode(0) dummy.next head prev, current dummy, head while current: if current.val val: prev.next current.next else: prev prev.next current current.next return dummy.next链表问题的解决关键在于对指针操作的深入理解和大量练习。通过本文介绍的各种算法和技巧相信你已经掌握了处理合并、交集、差集和奇偶分割等常见面试题的方法。在实际面试中记得先理清思路与面试官沟通确认需求再着手编写代码最后进行测试和优化。