链表基础原理与题目说明

链表基础原理与题目说明文章目录链表基础原理与题目说明一、 什么是链表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 → head1.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,val0,nextNone):self.valval# 数据域self.nextnext# 指针域# 定义双向链表节点如 LRU 缓存中会用到classDLinkedNode:def__init__(self,key0,value0):self.keykey# 键用于哈希表反向删除self.valuevalue self.preNone# 前驱指针self.nextNone# 后继指针2.2 链表基础流转操作# 1. 创建链表1 → 3 → 5 → Nonenode1ListNode(1)node2ListNode(3)node3ListNode(5)node1.nextnode2 node2.nextnode3 headnode1# 设定链表入口# 2. 插入节点在 1 和 3 之间插入 2new_nodeListNode(2)node1.nextnew_node new_node.nextnode2# 3. 删除节点删除节点 2node1.nextnode2# 节点1直接指向节点3跳过新节点# 4. 遍历链表currentheadwhilecurrent:print(current.val,end → )currentcurrent.next三、 基础操作与哈希表应用在链表的基础题目中哈希表Set/Dict常被用来记录节点的内存引用从而快速解决环路检测、相交判断及深拷贝问题。160. 相交链表解题思路存储链表 A 的所有节点引用而非节点值到哈希集合set中。随后遍历链表 B返回第一个在集合中命中的节点若无相交则返回None。核心代码fromtypingimportOptionalclassSolution:defgetIntersectionNode(self,headA:ListNode,headB:ListNode)-Optional[ListNode]:node_setset()currentheadA# 1. 记录链表A所有节点的内存引用whilecurrent:node_set.add(current)currentcurrent.next# 2. 遍历链表B寻找首个重合节点currentheadBwhilecurrent:ifcurrentinnode_set:returncurrent currentcurrent.nextreturnNone141. 环形链表 142. 环形链表 II解题思路利用哈希集合「存储节点引用 快速判断存在性」的特性。遍历链表若发现当前节点已存在于集合中则说明存在环返回 True 或该节点若遍历到None则无环。核心代码以142题寻找入环点为例fromtypingimportOptionalclassSolution:defdetectCycle(self,head:Optional[ListNode])-Optional[ListNode]:hashdictset()currentheadwhilecurrent:ifcurrentinhashdict:returncurrent# 找到入环点。如果是141题这里返回 Truehashdict.add(current)currentcurrent.nextreturnNone# 无环。如果是141题这里返回 False138. 随机链表的复制解题思路利用哈希表建立原节点 → 复制节点的映射。分两步复制先仅复制节点值建立映射再通过映射关系更新复制节点的next和random指针。使用dict.get()可完美兼容指针为None的边界情况。核心代码fromtypingimportOptionalclassSolution:defcopyRandomList(self,head:Optional[Node])-Optional[Node]:hashdict{}# 第一次遍历复制值构建映射cur_nodeheadwhilecur_node:hashdict[cur_node]Node(cur_node.val)cur_nodecur_node.next# 第二次遍历通过映射关系连接指针cur_nodeheadwhilecur_node:hashdict[cur_node].nexthashdict.get(cur_node.next)hashdict[cur_node].randomhashdict.get(cur_node.random)cur_nodecur_node.nextreturnhashdict.get(head)四、 链表中的双指针与虚拟头节点技巧234. 回文链表解题思路利用「数组可随机访问」的特性将链表的线性遍历转换为数组存储彻底解决单链表无法反向遍历的问题。随后利用左右双指针向中间靠拢判断回文。核心代码fromtypingimportOptionalclassSolution:defisPalindrome(self,head:Optional[ListNode])-bool:listarray[]currentheadwhilecurrent:listarray.append(current.val)currentcurrent.nextl,r0,len(listarray)-1whilelr:iflistarray[l]!listarray[r]:returnFalsel1r-1returnTrue21. 合并两个有序链表解题思路**虚拟头节点Dummy Node**是处理链表拼接的神技。双指针分别遍历两个链表逐个比较并拼接到虚拟头节点后最后追加未遍历完的剩余部分。核心代码fromtypingimportOptionalclassSolution:defmergeTwoLists(self,list1:Optional[ListNode],list2:Optional[ListNode])-Optional[ListNode]:temp_nodecur_nodeListNode(0)# 虚拟头节点whilelist1andlist2:iflist1.vallist2.val:cur_node.nextlist1 list1list1.nextelse:cur_node.nextlist2 list2list2.nextcur_nodecur_node.next# 拼接剩余有序部分cur_node.nextlist1iflist1elselist2returntemp_node.next2. 两数相加解题思路逆序存储天然契合“从个位数开始进位加法”的数学逻辑。维护一个进位标记carry双指针同步遍历。空节点按 0 处理直到两链表走完且进位为 0 时结束。核心代码fromtypingimportOptionalclassSolution:defaddTwoNumbers(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:dummycurListNode(0)carry0whilel1orl2orcarry:val1l1.valifl1else0val2l2.valifl2else0totalval1val2carry cur_valtotal%10carrytotal//10cur.nextListNode(cur_val)curcur.nextifl1:l1l1.nextifl2:l2l2.nextreturndummy.next19. 删除链表的倒数第 N 个结点解题思路利用栈Stack“先进后出”的特性此处分享栈解法快慢指针亦可。先将所有节点压入栈中随后弹出n个节点此时栈顶即为待删除节点的前驱节点。搭配虚拟头节点可完美处理删除原链表头节点的边界情况。核心代码fromtypingimportOptionalclassSolution:defremoveNthFromEnd(self,head:Optional[ListNode],n:int)-Optional[ListNode]:dummy_nodeListNode(0,head)stack[]# 所有节点入栈包含虚拟头currentdummy_nodewhilecurrent:stack.append(current)currentcurrent.next# 弹出后续的 n 个节点for_inrange(n):stack.pop()# 此时栈顶即为待删除节点的前驱pre_nodestack[-1]pre_node.nextpre_node.next.nextreturndummy_node.next五、 链表的高阶反转与交换206. 反转链表解题思路经典双指针迭代法。定义pre_node初始为None和cur_node初始为head。每次遍历时先用temp_node留住后继节点再原地将当前节点的next掉头指向前驱。核心代码fromtypingimportOptionalclassSolution:defreverseList(self,head:Optional[ListNode])-Optional[ListNode]:pre_nodeNonecur_nodeheadwhilecur_node:temp_nodecur_node.next# 留住后路cur_node.nextpre_node# 指针反转# 整体平移pre_nodecur_node cur_nodetemp_nodereturnpre_node24. 两两交换链表中的节点解题思路提供迭代法。借助虚拟头节点每次确保有两个相邻节点可交换cur.next与cur.next.next。在交换时注意指针断开与重连的顺序避免链表断裂。核心代码fromtypingimportOptionalclassSolution:defswapPairs(self,head:Optional[ListNode])-Optional[ListNode]:dummy_nodeListNode(0,head)cur_nodedummy_nodewhilecur_node.nextandcur_node.next.next:node1cur_node.nextnode2cur_node.next.next# 核心穿针引线逻辑cur_node.nextnode2 node1.nextnode2.nextnode2.nextnode1# 步进准备下一对cur_nodenode1returndummy_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_nodeNonecur_nodelwhilecur_node!r:next_nodecur_node.nextcur_node.nextpre_node pre_nodecur_node cur_nodenext_nodereturnpre_nodeifnothead:returnNonelrhead# 寻找当前组的右边界for_inrange(k):ifnotr:returnhead# 不足 k 个保持原样返回rr.next# 翻转当前组newheadreverselr(l,r)# 递归衔接剩余链表l.nextself.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_nodecur_nodeListNode(0)whilelist1andlist2:iflist1.vallist2.val:cur_node.nextlist1 list1list1.nextelse:cur_node.nextlist2 list2list2.nextcur_nodecur_node.nextcur_node.nextlist1iflist1elselist2returndummy_node.nextansNoneforlinlists:ansmerge2list(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,fasthead,head.nextwhilefastandfast.next:slowslow.nextfastfast.next.next# 2. 截断链表分为两半midslow.nextslow.nextNone# 3. 分别递归排序left_listself.sortList(head)right_listself.sortList(mid)# 4. 合并两个有序链表dummy_nodecur_nodeListNode(0)whileleft_listandright_list:ifleft_list.valright_list.val:cur_node.nextleft_list left_listleft_list.nextelse:cur_node.nextright_list right_listright_list.nextcur_nodecur_node.nextcur_node.nextleft_listifleft_listelseright_listreturndummy_node.next七、 综合数据结构设计146. LRU 缓存解题思路LRU 缓存机制的灵魂在于哈希表 双向链表。哈希表Dict解决“快速查找”通过 Key 在O ( 1 ) O(1)O(1)时间内定位到内存中的链表节点。双向链表DLinkedNode解决“快速变动”用于维护基于时间序列的使用顺序。链表头部代表最近访问尾部代表最久未访问。伪头/伪尾哨兵节点极大简化在链表两端增删元素时的越界判断。核心代码classDLinkedNode:def__init__(self,key0,value0):self.keykey# 冗余存储key用于淘汰时反向删除哈希表记录self.valuevalue self.preNoneself.nextNoneclassLRUCache:def__init__(self,capacity:int):self.hashcachedict()self.capacitycapacity self.size0# 初始化伪头和伪尾节点互相连接构成初始边界self.headDLinkedNode()self.tailDLinkedNode()self.head.nextself.tail self.tail.preself.headdefget(self,key:int)-int:ifkeynotinself.hashcache:return-1nodeself.hashcache[key]self.moveToHead(node)# 访问过提升为最近使用returnnode.valuedefput(self,key:int,value:int)-None:ifkeynotinself.hashcache:nodeDLinkedNode(key,value)self.hashcache[key]node self.addToHead(node)self.size1# 若超限移除队尾最久未使用节点ifself.sizeself.capacity:remove_nodeself.removeTail()self.hashcache.pop(remove_node.key)self.size-1else:nodeself.hashcache[key]node.valuevalue self.moveToHead(node)# 内部辅助指针操作 defaddToHead(self,node):node.preself.head node.nextself.head.nextself.head.next.prenode self.head.nextnodedefremoveNode(self,node):node.pre.nextnode.nextnode.next.prenode.predefmoveToHead(self,node):self.removeNode(node)self.addToHead(node)defremoveTail(self):nodeself.tail.pre self.removeNode(node)returnnode