了解链表1. 什么是链表链表是一种通过指针串联在一起的线性结构每一个节点由两部分组成一个是数据域一个是指针域存放指向下一个节点的指针最后一个节点的指针域指向null空指针的意思。2. Python中实现链表的生成class ListNode: 链表的节点类 def __init__(self, val0, nextNone): self.val val # 数据域存数据 self.next next # 指针域存下一个节点的引用 # 手动构建一个链表: 1 - 2 - 3 node3 ListNode(3) # 尾节点next 默认 None node2 ListNode(2, node3) # node2.next node3 node1 ListNode(1, node2) # node1.next node2 head node1 # head 指向第一个节点首先先说明几个点1.头节点指的是第一个节点而head不是头节点他只是指向头节点的一个变量Leecode和python算法中是这么定义的而传统教材认为头节点就是head这里我们认为头节点是第一个有效节点。head认为是头而node1是头节点2. 最后一个节点我们代码定义里面是node3 ListNode(3)只有val然后next看上面的定义函数nextNone如果不赋值就是None所以最后一个节点指向是空。3.head对应的就是头节点的地址所以比如说Xhead就是把头节点的地址赋值给X。3. 链表的类型1.单链表也就是我们上面定义的这种2.双链表双链表每一个节点有两个指针域一个指向下一个节点一个指向上一个节点。双链表 既可以向前查询也可以向后查询。3.循环链表循环链表顾名思义就是链表首尾相连。循环链表可以用来解决约瑟夫环问题。4. 链表的存储方法数组是在内存中是连续分布的但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的 而是散乱分布在内存中的某地址上分配机制取决于操作系统的内存管理。5. 链表的定义class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextnode ListNode(5) # val5, nextNone head ListNode(5, node2) # val5, nextnode2 empty ListNode() # val0, nextNone全用默认值6. 链表的操作1. 删除节点删除D节点C.next E # 或者写成 C.next D.nextpython中不需要吧D节点删除会自动回收节点而C之类的需要自己手动删除该节点即delete D但是注意删除操作是O(1)但是还需要找到前驱节点C是O(n)# 假设要删除值为 target 的节点 cur head while cur and cur.next: if cur.next.val target: cur.next cur.next.next # O(1) 删除 break # Python 自动回收被跳过的节点 cur cur.next # O(n) 查找2. 添加节点2.1 在节点C之后插入XX.next C.next # 先接后面顺序不能反 C.next X # 再接前面注意顺序否则会导致链表断裂2.2 在头节点插入X.next head head X # head 指向新节点注意head对应的就是原本头节点的地址直接赋值给X就行7. 链表和数组的性能分析操作数组链表本质原因插入/删除O(n) ⚠️O(1) ✅数组需搬移后续元素链表只需改指针查询按索引O(1) ✅O(n) ⚠️数组连续内存可直接计算地址链表必须遍历适用场景数据量固定、频繁查询、较少增删数据量不固定、频繁增删、较少查询选型黄金法则移除链表元素题目给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5] 示例 2 输入head [], val 1 输出[] 示例 3 输入head [7,7,7,7], val 7 输出[] 提示 列表中的节点数目在范围 [0, 104] 内 1 Node.val 50 0 val 50思路引入dummy作为头的头然后再使用cur作为一个指针来进行删除操作最后返回头引伸出来的问题-应该是后面所有链表通用的问题1. dummy是啥这是个虚拟头指向的是头即头的头。2. 为什么需要curcur是一个指针用来进行删除中间的一些值。为什么不直接使用dummy因为如果直接用dummy我们后面就找不到头了因为dummy会跑到最后去。3. 为什么用dummy而不是直接使用原来的头因为如果使用原来的头就会出现一个问题当头节点是我们需要删除的那么就会出现我们头已经往后走了我们需要知道前面一个节点才能修改而使用头的头就不需要考虑这个问题了。尤其是出现前几个都是需要删除的时候我们还需要使用while循环一直判断是不是val然后一直跳过并且代码会出现割裂一会使用head一会使用cur。4. dummy和cur是同一地址空间是的cur指向的是dummy他们是同一地址空间5. 为什么使用dummy.next而不是head因为这里是值拷贝而不是引用绑定dummy ListNode(nexthead)只是把头节点的地址拷贝过来了即dummy.next是6的地址而head和dummy是两个变量了。6. 个人理解一下head是第一个头节点的地址而dummy.next是第一个头节点的地址所以dummy.nexthead第一个头节点地址。但是这里只是地址而不是说dummy.nexthead因为head不是节点。然后链表是用地址链接的head只是一个地址我们改的是dummy.next而不是head。7. 索引问题第一个头指针的索引是0而不是1代码# Definition for singly-linked list. class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def removeElements(self, head: ListNode, val: int) - ListNode: # 1. 创建 dummy 节点next 指向原头节点 dummy ListNode(nexthead) # 2. cur 从 dummy 开始遍历cur 始终是被检查节点的前驱 cur dummy while cur.next: if cur.next.val val: # 删除操作跳过目标节点cur 不动因为新的 cur.next 还没检查 cur.next cur.next.next else: # 当前 cur.next 不是目标cur 安全前进 cur cur.next # 3. 返回 dummy.next即新链表的真正头节点 return dummy.next题目链接203. 移除链表元素 - 力扣LeetCode设计链表题目你可以选择使用单链表或者双链表设计并实现自己的链表。 单链表中的节点应该具备两个属性val 和 next 。val 是当前节点的值next 是指向下一个节点的指针/引用。 如果是双向链表则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。 实现 MyLinkedList 类 MyLinkedList() 初始化 MyLinkedList 对象。 int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效则返回 -1 。 void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后新节点会成为链表的第一个节点。 void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。 void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度那么该节点会被追加到链表的末尾。如果 index 比长度更大该节点将 不会插入 到链表中。 void deleteAtIndex(int index) 如果下标有效则删除链表中下标为 index 的节点。代码class ListNode(object): def __init__(self, val0, nextNone): self.val val self.next next class MyLinkedList(object): def __init__(self): self.dummy ListNode() self.size 0 def get(self, index): :type index: int :rtype: int if index 0 or index self.size: return -1 cur self.dummy.next for _ in range(index): cur cur.next return cur.val def addAtHead(self, val): :type val: int :rtype: None self.dummy.next ListNode(val, self.dummy.next) self.size 1 def addAtTail(self, val): :type val: int :rtype: None cur self.dummy while cur.next: cur cur.next cur.next ListNode(val) self.size 1 def addAtIndex(self, index, val): :type index: int :type val: int :rtype: None # ✅ 核心修复此处必须判断 index而非 val # 允许在尾部追加所以是 而不是 if index 0 or index self.size: return cur self.dummy for _ in range(index): cur cur.next cur.next ListNode(val, cur.next) self.size 1 def deleteAtIndex(self, index): :type index: int :rtype: None if index 0 or index self.size: return cur self.dummy for _ in range(index): cur cur.next cur.next cur.next.next self.size - 1 # Your MyLinkedList object will be instantiated and called as such: # obj MyLinkedList() # param_1 obj.get(index) # obj.addAtHead(val) # obj.addAtTail(val) # obj.addAtIndex(index,val) # obj.deleteAtIndex(index)难点1. 判断大于还是大于等于2. self.size的使用可以防止每次都循环遍历查链表长度3. dummy不计入因为self.dummy ListNode() self.size 0这样子赋值的题目链接707. 设计链表 - 力扣LeetCode反转列表推荐直接看视频然后来写代码【帮你拿下反转链表 | LeetCode206.反转链表 | 双指针法 | 递归法】https://www.bilibili.com/video/BV1nB4y1i7eL?vd_sourcea645f71d9fefc256478e13ce6e9c2602题目题意反转一个单链表。 示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL思路第一种思路反转列表然后两个指针cur表示当前pre表示前一个还需要一个临时指针保存cur的位置不然反转的时候连不上了。然后思路就是看那个视频说的还是比较清晰的第二种思路是递归就是把上一个思路进行递归当然递归需要注意递归的参数递归的停止条件这个很重要代码双指针法# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: prev None cur head while cur is not None: nxt cur.next # 1. 暂存下一个节点防止断链 cur.next prev # 2. 翻转当前节点的指向 prev cur # 3. prev 前进一步 cur nxt # 4. cur 前进一步 return prev # 循环结束时 curNoneprev 就是新的头节点递归法class Solution: def reverseList(self, head: ListNode) - ListNode: return self.reverse(None, head) def reverse(self, pre: ListNode, cur: ListNode) - ListNode: if cur is None: # 对应 while cur: 的终止条件 return pre temp cur.next # 保存下一个节点 cur.next pre # 翻转 return self.reverse(cur, temp) # 对应 precur; curtemp1. if cur is None: 这是递归的重点找到终止条件2. temp cur.next cur.next pre 这一步就是前面的存节点然后反转3. return self.reverse(cur, temp) 这步看着很懵但是其实就是pre cur cur next但是我没有这样赋值因为我可以直接用递归调用里面也有参数也就是pre和cur我直接把cur和next对应放进去就是赋值了。 或者你也可以多一步pre cur cur next然后self.reverse(pre,cur) 本质是一样的只是这里少了这步直接我们就放进去了题目链接206. 反转链表 - 力扣LeetCode