把链表操作从基础操作到算法进行分析主要总结一下写力扣链表时学到的链表操作因为是练习Python所以所有操作都是围绕Python的语法。基础操作要学习链表首先要了解链表核心本质不连续内存靠指针/引用串联节点只有头指针访问任意节点必须从头遍历擅长插入删除不擅长随机访问。使用单链表进行节点定义每个节点包含 val 数值和 next 指向下一个节点的引用。class ListNode: def __init__(self, val0, nextNone): self.val val # 节点存储的数据 self.next next # 引用存下一个节点对象None代表链表末尾1、插入节点最简单的就是手动逐个创建。# 1. 创建3个节点对象此时互相独立没有连接 node1 ListNode(1) node2 ListNode(2) node3 ListNode(3) # 2. 修改节点内部next把节点串起来 node1.next node2 # node1的next保存node2的引用 node2.next node3 # node2的next保存node3的引用 node3.next None # 尾节点后面没有节点默认就是None可以省略 # head头引用保存链表起点用来找到整个链表 head node1头指针千万要记得保存head就像是访问一个链表的入口。还有尾插法尾插法是最常用的方法。def create_linked_list(arr): dummy ListNode() # 哑节点不存有效数据 tail dummy # tail初始指向dummy for num in arr: new_node ListNode(num) tail.next new_node # 把新节点接到尾部 tail new_node # tail移动tail现在是新的尾节点 return dummy.next # dummy.next才是链表真正头节点 # 使用 head create_linked_list([1,2,3,4])首先新建哑结点 dummy 方便处理空链表tail 指针永远指向链表的最后一个节点然后遍历传进来的数组不断新建节点挂在 tail 的后面tail 向后移动。链表还有头插法这里就不过多赘述了链表的基础应该都多多少少了解一点。2、遍历链表遍历链表用临时变量 cur从头结点开始不断向后走。def traverse(head: ListNode): cur head # cur拿到head当前的引用cur指向头节点 while cur is not None: print(cur.val) # 读取当前节点的值 cur cur.next # 拷贝cur.next里面保存的引用赋值给curcur移动到下一个节点 # 注意这行只修改cur这个外部变量完全不改动链表节点 traverse(head) # 输出1 2 33、查询节点def find_node(head: ListNode, target): cur head while cur: if cur.val target: return cur # 返回节点引用可以用来修改节点 cur cur.next return None # 没找到 res find_node(head, 2) print(res.val) # 24、删除节点def delete_node(head: ListNode, target): # 情况1头节点就是要删除的节点 if head.val target: return head.next # 新头节点是原head.next原头节点脱离链表 # 情况2找前驱节点 prepre.next 是待删节点 pre head # pre.next 不为空并且 pre.next.val ! target继续往后走 while pre.next is not None and pre.next.val ! target: pre pre.next # pre.next 就是待删节点 pre.next pre.next.next # 跳过待删节点直接连接下一个节点 return head head delete_node(head, 2.5) # 0-1-2-3-45、修改节点的值def modify_node(head: ListNode, old_val, new_val): cur find_node(head, old_val) if cur: cur.val new_val # 修改节点对象内部的值所有指向该节点的引用都能看到变化 return head head modify_node(head, 3, 99) # 0-1-2-99-4一、链表核心指针技巧1、虚拟头结点dummy在刷题过程中虚拟头结点使用频率很频繁在删除节点、新建链表、合并链表的时候常常会有边界问题为了避免单独处理第一个节点的边界情况就会使用虚拟头结点。# 创建虚拟头结点val随便写一般0不重要 dummy ListNode(0) # dummy.next 指向原链表头 head dummy.next head # 遍历指针cur初始指向dummy从dummy开始遍历 cur dummy简化版本dummy ListNode(0, head) cur dummy对于dummy是否指向head要判断dummy是用来接管已有链表还是用来新建一个空链表。情况1已有链表要修改原链表dummy ListNode(0, head) # dummy.next head cur dummy while cur.next: if cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy.next情况2从头构建全新链表dummy ListNode(0) # dummy.next 默认 None没有接任何链表 cur dummy while list1 and list2: if list1.val list2.val: cur.next list1 list1 list1.next else: cur.next list2 list2 list2.next cur cur.next cur.next list1 if list1 else list2 return dummy.next2、快慢双指针双指针在算法题目里出现的次数非常多主要用法有两种一种是快慢指针另外一种是滑动指针两个指针并行。1、找链表中点快指针一次走2步慢指针一次走1步。快到末尾时慢指针在中点。def middleNode(head: ListNode) - ListNode: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow2、判断链表是否有环找环入口原理就是有环的话快慢指针会相遇相遇之后再让一个指针从头出发慢指针从相遇点继续走新指针和慢指针遇到的交点就是入口具体数学推导在之前的题目解法里面。# 判断是否有环 def hasCycle(head: ListNode) - bool: slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False # 找环入口 def detectCycle(head: ListNode) - ListNode: slow, fast head, head has_cycle False while fast and fast.next: slow slow.next fast fast.next.next if slow fast: has_cycle True break if not has_cycle: return None p head while p ! slow: p p.next slow slow.next return p3、前后双指针前驱节点 pre 当前节点 cur一般用在链表反转、原地删除节点。需要理解并且记住顺序存 next →改变指向→ pre 移动→ cur 移动下面这个就是反转链表的代码def reverseList(head: ListNode) - ListNode: pre None cur head while cur: nxt cur.next # 先保存下一个节点非常关键不然断链 cur.next pre # 当前节点反向指向前一个 pre cur # pre前移 cur nxt # cur前移 return pre4、双指针分离 / 合并链表合并的代码如下这个比较好理解。def mergeTwoLists(list1: ListNode, list2: ListNode) - ListNode: dummy ListNode() cur dummy while list1 and list2: if list1.val list2.val: cur.next list1 list1 list1.next else: cur.next list2 list2 list2.next cur cur.next # 接上剩余部分 cur.next list1 if list1 else list2 return dummy.next5、多指针反转链表区间反转链表的进阶版在某个区间进行反转需要precurnxt主要需要判断反转的左右边界在K个一组翻转链表中还要判断一下剩余节点是否满足反转条件。下面代码为反转 left 到 right 个节点。def reverseBetween(head: ListNode, left: int, right: int) - ListNode: dummy ListNode(nexthead) pre dummy # pre走到left前一个节点 for _ in range(left - 1): pre pre.next cur pre.next # 开始反转一共反转 right-left 次 for _ in range(right - left): nxt cur.next cur.next nxt.next nxt.next pre.next pre.next nxt return dummy.next6、指针的核心坑点主要是我刚开始接触指针时遇到的一些问题。1、变量赋值是拷贝引用不是绑定a ListNode(1) b a b None # a不会变b只是拷贝了a的引用b赋值None只是b不再指向节点指针的变量赋值变量是指向变量的引用相当于指向同一个地址不是指向这个变量本身变量的修改不会影响链表对象只有修改节点属性才会改动链表对象a.next xxx2、断链风险移动指针前一定要提前保存next不然会丢了后面链表同样的在翻转链表时也要设置pre让上一个反转的和后一个已经翻转的节点连接。3、空指针判断循环条件优先 fast and fast.next防止 fast.next.next 报 None 报错。二、其它逻辑结构的应用1、哈希集合遍历链表每访问一个节点存入set每次先判断当前节点是否已经在集合中。集合中存的是节点对象的引用不是拷贝一份新节点对象本身还在原来的内存里所以节点所有属性全都保留能直接访问。下面是判断环的代码。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def hasCycle(head: ListNode) - bool: visited set() cur head while cur: if cur in visited: return True visited.add(cur) cur cur.next return False2、哈希字典随机链表复制就是字典经典题首先要遍历一下原链表创建新节点建立原节点到新节点映射关系存入字典然后再次遍历原链表通过字典给新节点的 next 和 random 赋值字典只负责原链表和新链表的配对。# 第一轮 cur head while cur: # 创建新节点新节点.val cur.valnextNonerandomNone old2new[cur] Node(cur.val) cur cur.next第一轮1、开辟内存生成新节点对象这个对象有val、next、random 三个属性只是 next 和 random 现在还是None。2、往字典里写入映射原节点 cur → 刚创建好的新节点。# 第二轮 cur head while cur: # old2new[cur] 拿到对应的新节点 old2new[cur].next old2new.get(cur.next, None) old2new[cur].random old2new.get(cur.random, None) cur cur.next第二轮遍历原链表查找映射表给新节点的 next、random 赋值。old2new.get(cur.next) cur.next 是原链表的下一个原节点去字典查到它对应的新节点赋值给新节点的 next 。3、链表 栈栈常用的使用场景有回文所以可以用在回文链表判断是否是回文链表需要全部压栈再遍历链表对比栈弹出的值。如果想了解更多栈的用法可以继续刷题后面有单独栈的模块。def isPalindrome(head: ListNode) - bool: stack [] cur head while cur: stack.append(cur.val) cur cur.next cur head while stack: if cur.val ! stack.pop(): return False cur cur.next return True也可以用链表自身实现栈头插法在链表头部进行增删。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Stack: def __init__(self): self.head None def push(self, val): # 头插 new_node ListNode(val) new_node.next self.head self.head new_node def pop(self): if not self.head: return None val self.head.val self.head self.head.next return val def peek(self): return self.head.val if self.head else None4、链表 队列用链表自己实现队列用链表作为底层存储实现队列队列就是尾插头删。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Queue: def __init__(self): self.head None self.tail None def enqueue(self, val): new_node ListNode(val) if not self.tail: self.head new_node self.tail new_node else: self.tail.next new_node self.tail new_node def dequeue(self): if not self.head: return None val self.head.val self.head self.head.next if not self.head: self.tail None return val我目前刷题遇到的知识点只有这些等以后刷题多了再补充另外栈堆知识等以后刷到具体模块再总结。