深入解析Camunda中BPMN 2.0监听器的实现与应用场景
2026/4/18 5:05:15
链表基础原理与题目说明
文章目录
- 链表基础原理与题目说明
- 一、 什么是链表？
- 1.1 链表的组成与分类
- 1.2 链表 vs 数组核心对比
- 二、 Python 中的链表实现与基础操作
- 2.1 单向/双向节点定义
- 2.2 链表基础流转操作
- 三、 基础操作与哈希表应用
- [160. 相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/)
- [141. 环形链表](https://leetcode.cn/problems/linked-list-cycle/) & [142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/)
- [138. 随机链表的复制](https://leetcode.cn/problems/copy-list-with-random-pointer/)
- 四、 链表中的双指针与虚拟头节点技巧
- [234. 回文链表](https://leetcode.cn/problems/palindrome-linked-list/)
- [21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/)
- [2. 两数相加](https://leetcode.cn/problems/add-two-numbers/)
- [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)
- 五、 链表的高阶反转与交换
- [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)
- [24. 两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/)
- [25. K 个一组翻转链表](https://leetcode.cn/problems/reverse-nodes-in-k-group/)
- 六、 链表的排序与合并
- [23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/)
- [148. 排序链表](https://leetcode.cn/problems/sort-list/)
- 七、 综合数据结构设计
- [146. LRU 缓存](https://leetcode.cn/problems/lru-cache/)
🔗 查看完整专栏（LeetCode基础算法专栏）
特别说明：
本文为个人的 LeetCode 刷题与学习笔记，内容仅供学习与交流使用，禁止转载或用于商业用途。需要强调的是，文中的题目解法不一定是最优解（可能存在时间或空间复杂度的进一步优化空间），主要目的是分享个人的解题思路与逻辑实现，仅供参考。笔记内容为个人理解与总结，可能存在疏漏或偏差，欢迎读者自行甄别并交流探讨。
一、 什么是链表？
链表（Linked List）是一种线性数据结构。与数组不同，链表中的元素在内存中并不是连续存储的，而是依靠指针引用把零散的节点（Node）串联起来。
1.1 链表的组成与分类
以最常见的单链表为例，每个节点通常包含两部分：
- 数据域（val）：存储实际的值（如数字、字符串）。
- 指针域（next）：存储下一个节点的内存地址（引用），相当于“指向”下一个节点的“箭头”。
| 链表类型 | 特点说明 | 结构示意图 |
|---|---|---|
| 单链表 | 节点只有next指针，只能单向顺序遍历。 | head → Node1 → Node2 → None |
| 双向链表 | 节点包含prev和next指针，支持双向遍历。 | None ← Node1 ↔ Node2 ↔ Node3 → None |
| 循环链表 | 尾节点的next指向头节点，形成逻辑闭环。 | head → Node1 → Node2 → head |
1.2 链表 vs 数组核心对比
| 对比维度 | 数组（Array） | 链表（Linked List） |
|---|---|---|
| 存储方式 | 内存中连续分配 | 内存中零散分配，靠指针串联 |
| 访问元素 | 随机访问，时间复杂度O ( 1 ) O(1)O(1) | 顺序访问，必须从头遍历，时间复杂度O ( n ) O(n)O(n) |
| 插入/删除 | 需移动后续大量元素，时间复杂度O ( n ) O(n)O(n) | 只需修改相邻指针，时间复杂度O ( 1 ) O(1)O(1) |
| 空间占用 | 长度固定（动态数组存在扩容开销），易浪费 | 按需动态分配，但每个节点需额外存储指针（空间开销略大） |
二、 Python 中的链表实现与基础操作
Python 没有内置的原生链表结构，但可以通过面向对象中的「类」来完美模拟节点与链表操作。
2.1 单向/双向节点定义
# 定义单链表节点classListNode:def__init__(self,val=0,next=None):self.val=val# 数据域self.next=next# 指针域# 定义双向链表节点（如 LRU 缓存中会用到）classDLinkedNode:def__init__(self,key=0,value=0):self.key=key# 键（用于哈希表反向删除）self.value=value self.pre=None# 前驱指针self.next=None# 后继指针2.2 链表基础流转操作
# 1. 创建链表：1 → 3 → 5 → Nonenode1=ListNode(1)node2=ListNode(3)node3=ListNode(5)node1.next=node2 node2.next=node3 head=node1# 设定链表入口# 2. 插入节点：在 1 和 3 之间插入 2new_node=ListNode(2)node1.next=new_node new_node.next=node2# 3. 删除节点：删除节点 2node1.next=node2# 节点1直接指向节点3，跳过新节点# 4. 遍历链表current=headwhilecurrent:print(current.val,end=" → ")current=current.next三、 基础操作与哈希表应用
在链表的基础题目中，哈希表（Set/Dict）常被用来记录节点的内存引用，从而快速解决环路检测、相交判断及深拷贝问题。
160. 相交链表
解题思路：
存储链表 A 的所有节点引用（而非节点值）到哈希集合set中。随后遍历链表 B，返回第一个在集合中命中的节点；若无相交则返回None。
核心代码：
fromtypingimportOptionalclassSolution:defgetIntersectionNode(self,headA:ListNode,headB:ListNode)->Optional[ListNode]:node_set=set()current=headA# 1. 记录链表A所有节点的内存引用whilecurrent:node_set.add(current)current=current.next# 2. 遍历链表B寻找首个重合节点current=headBwhilecurrent:ifcurrentinnode_set:returncurrent current=current.nextreturnNone141. 环形链表 & 142. 环形链表 II
解题思路：
利用哈希集合「存储节点引用 + 快速判断存在性」的特性。遍历链表，若发现当前节点已存在于集合中，则说明存在环（返回 True 或该节点）；若遍历到None，则无环。
核心代码（以142题寻找入环点为例）：
fromtypingimportOptionalclassSolution:defdetectCycle(self,head:Optional[ListNode])->Optional[ListNode]:hashdict=set()current=headwhilecurrent:ifcurrentinhashdict:returncurrent# 找到入环点。如果是141题，这里返回 Truehashdict.add(current)current=current.nextreturnNone# 无环。如果是141题，这里返回 False138. 随机链表的复制
解题思路：
利用哈希表建立原节点 → 复制节点的映射。分两步复制：先仅复制节点值（建立映射），再通过映射关系更新复制节点的next和random指针。使用dict.get()可完美兼容指针为None的边界情况。
核心代码：
fromtypingimportOptionalclassSolution:defcopyRandomList(self,head:'Optional[Node]')->'Optional[Node]':hashdict={}# 第一次遍历：复制值，构建映射cur_node=headwhilecur_node:hashdict[cur_node]=Node(cur_node.val)cur_node=cur_node.next# 第二次遍历：通过映射关系连接指针cur_node=headwhilecur_node:hashdict[cur_node].next=hashdict.get(cur_node.next)hashdict[cur_node].random=hashdict.get(cur_node.random)cur_node=cur_node.nextreturnhashdict.get(head)四、 链表中的双指针与虚拟头节点技巧
234. 回文链表
解题思路：
利用「数组可随机访问」的特性，将链表的线性遍历转换为数组存储，彻底解决单链表无法反向遍历的问题。随后利用左右双指针向中间靠拢判断回文。
核心代码：
fromtypingimportOptionalclassSolution:defisPalindrome(self,head:Optional[ListNode])->bool:listarray=[]current=headwhilecurrent:listarray.append(current.val)current=current.nextl,r=0,len(listarray)-1whilel<=r:iflistarray[l]!=listarray[r]:returnFalsel+=1r-=1returnTrue21. 合并两个有序链表
解题思路：
**虚拟头节点（Dummy Node）**是处理链表拼接的神技。双指针分别遍历两个链表，逐个比较并拼接到虚拟头节点后，最后追加未遍历完的剩余部分。
核心代码：
fromtypingimportOptionalclassSolution:defmergeTwoLists(self,list1:Optional[ListNode],list2:Optional[ListNode])->Optional[ListNode]:temp_node=cur_node=ListNode(0)# 虚拟头节点whilelist1andlist2:iflist1.val<list2.val:cur_node.next=list1 list1=list1.nextelse:cur_node.next=list2 list2=list2.nextcur_node=cur_node.next# 拼接剩余有序部分cur_node.next=list1iflist1elselist2returntemp_node.next2. 两数相加
解题思路：
逆序存储天然契合“从个位数开始进位加法”的数学逻辑。维护一个进位标记carry，双指针同步遍历。空节点按 0 处理，直到两链表走完且进位为 0 时结束。
核心代码：
fromtypingimportOptionalclassSolution:defaddTwoNumbers(self,l1:Optional[ListNode],l2:Optional[ListNode])->Optional[ListNode]:dummy=cur=ListNode(0)carry=0whilel1orl2orcarry:val1=l1.valifl1else0val2=l2.valifl2else0total=val1+val2+carry cur_val=total%10carry=total//10cur.next=ListNode(cur_val)cur=cur.nextifl1:l1=l1.nextifl2:l2=l2.nextreturndummy.next19. 删除链表的倒数第 N 个结点
解题思路：
利用栈（Stack）“先进后出”的特性（此处分享栈解法，快慢指针亦可）。先将所有节点压入栈中，随后弹出n个节点，此时栈顶即为待删除节点的前驱节点。搭配虚拟头节点可完美处理删除原链表头节点的边界情况。
核心代码：
fromtypingimportOptionalclassSolution:defremoveNthFromEnd(self,head:Optional[ListNode],n:int)->Optional[ListNode]:dummy_node=ListNode(0,head)stack=[]# 所有节点入栈（包含虚拟头）current=dummy_nodewhilecurrent:stack.append(current)current=current.next# 弹出后续的 n 个节点for_inrange(n):stack.pop()# 此时栈顶即为待删除节点的前驱pre_node=stack[-1]pre_node.next=pre_node.next.nextreturndummy_node.next五、 链表的高阶反转与交换
206. 反转链表
解题思路：
经典双指针迭代法。定义pre_node（初始为None）和cur_node（初始为head）。每次遍历时，先用temp_node留住后继节点，再原地将当前节点的next掉头指向前驱。
核心代码：
fromtypingimportOptionalclassSolution:defreverseList(self,head:Optional[ListNode])->Optional[ListNode]:pre_node=Nonecur_node=headwhilecur_node:temp_node=cur_node.next# 留住后路cur_node.next=pre_node# 指针反转# 整体平移pre_node=cur_node cur_node=temp_nodereturnpre_node24. 两两交换链表中的节点
解题思路：
提供迭代法。借助虚拟头节点，每次确保有两个相邻节点可交换（cur.next与cur.next.next）。在交换时，注意指针断开与重连的顺序，避免链表断裂。
核心代码：
fromtypingimportOptionalclassSolution:defswapPairs(self,head:Optional[ListNode])->Optional[ListNode]:dummy_node=ListNode(0,head)cur_node=dummy_nodewhilecur_node.nextandcur_node.next.next:node1=cur_node.nextnode2=cur_node.next.next# 核心穿针引线逻辑cur_node.next=node2 node1.next=node2.nextnode2.next=node1# 步进，准备下一对cur_node=node1returndummy_node.next(注：本题也可以采用递归拆解子问题：处理当前对节点的交换，剩余链表交由递归完成拼接)
25. K 个一组翻转链表
解题思路：
分治与递归思想。自定义reverselr(l, r)函数实现左闭右开区间[l, r)的就地反转。主函数中通过循环定位k个元素的右边界，调用反转函数，并将反转后的尾节点衔接下一轮递归返回的结果。
核心代码：
fromtypingimportOptionalclassSolution:defreverseKGroup(self,head:Optional[ListNode],k:int)->Optional[ListNode]:# 辅助函数：翻转 [l, r) 区间内的节点defreverselr(l,r):pre_node=Nonecur_node=lwhilecur_node!=r:next_node=cur_node.nextcur_node.next=pre_node pre_node=cur_node cur_node=next_nodereturnpre_nodeifnothead:returnNonel=r=head# 寻找当前组的右边界for_inrange(k):ifnotr:returnhead# 不足 k 个，保持原样返回r=r.next# 翻转当前组newhead=reverselr(l,r)# 递归衔接剩余链表l.next=self.reverseKGroup(r,k)returnnewhead六、 链表的排序与合并
23. 合并 K 个升序链表
解题思路：
将“合并 K 个”降维打击为“多次合并两个”。复用两两合并的代码逻辑，通过一个初始为None的结果链表，遍历列表数组不断累积合并。（也可使用优先队列优化至O ( N log K ) O(N \log K)O(NlogK)）
核心代码：
fromtypingimportList,OptionalclassSolution:defmergeKLists(self,lists:List[Optional[ListNode]])->Optional[ListNode]:# 辅助函数：合并两个升序链表defmerge2list(list1,list2):dummy_node=cur_node=ListNode(0)whilelist1andlist2:iflist1.val<list2.val:cur_node.next=list1 list1=list1.nextelse:cur_node.next=list2 list2=list2.nextcur_node=cur_node.nextcur_node.next=list1iflist1elselist2returndummy_node.nextans=Noneforlinlists:ans=merge2list(ans,l)returnans148. 排序链表
解题思路：
采用自顶向下的归并排序，满足O ( N log N ) O(N \log N)O(NlogN)复杂度要求。利用快慢指针找中点将链表一分为二（务必将前一段的next截断置空），分别递归排序，最后再合并有序链表。
核心代码：
fromtypingimportOptionalclassSolution:defsortList(self,head:Optional[ListNode])->Optional[ListNode]:ifheadisNoneorhead.nextisNone:returnhead# 1. 快慢指针找中点slow,fast=head,head.nextwhilefastandfast.next:slow=slow.nextfast=fast.next.next# 2. 截断链表分为两半mid=slow.nextslow.next=None# 3. 分别递归排序left_list=self.sortList(head)right_list=self.sortList(mid)# 4. 合并两个有序链表dummy_node=cur_node=ListNode(0)whileleft_listandright_list:ifleft_list.val<right_list.val:cur_node.next=left_list left_list=left_list.nextelse:cur_node.next=right_list right_list=right_list.nextcur_node=cur_node.nextcur_node.next=left_listifleft_listelseright_listreturndummy_node.next七、 综合数据结构设计
146. LRU 缓存
解题思路：
LRU 缓存机制的灵魂在于：哈希表 + 双向链表。
- 哈希表（Dict）：解决“快速查找”，通过 Key 在O ( 1 ) O(1)O(1)时间内定位到内存中的链表节点。
- 双向链表（DLinkedNode）：解决“快速变动”，用于维护基于时间序列的使用顺序。链表头部代表最近访问，尾部代表最久未访问。
- 伪头/伪尾哨兵节点：极大简化在链表两端增删元素时的越界判断。
核心代码：
classDLinkedNode:def__init__(self,key=0,value=0):self.key=key# 冗余存储key，用于淘汰时反向删除哈希表记录self.value=value self.pre=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.hashcache=dict()self.capacity=capacity self.size=0# 初始化伪头和伪尾节点，互相连接构成初始边界self.head=DLinkedNode()self.tail=DLinkedNode()self.head.next=self.tail self.tail.pre=self.headdefget(self,key:int)->int:ifkeynotinself.hashcache:return-1node=self.hashcache[key]self.moveToHead(node)# 访问过，提升为最近使用returnnode.valuedefput(self,key:int,value:int)->None:ifkeynotinself.hashcache:node=DLinkedNode(key,value)self.hashcache[key]=node self.addToHead(node)self.size+=1# 若超限，移除队尾（最久未使用）节点ifself.size>self.capacity:remove_node=self.removeTail()self.hashcache.pop(remove_node.key)self.size-=1else:node=self.hashcache[key]node.value=value self.moveToHead(node)# =============== 内部辅助指针操作 ===============defaddToHead(self,node):node.pre=self.head node.next=self.head.nextself.head.next.pre=node self.head.next=nodedefremoveNode(self,node):node.pre.next=node.nextnode.next.pre=node.predefmoveToHead(self,node):self.removeNode(node)self.addToHead(node)defremoveTail(self):node=self.tail.pre self.removeNode(node)returnnode