网站空间地址查询,阿里云wordpress配置,wordpress缓存类,青岛哪家公司做网站好数据结构刷题-链表 总结#xff1a;1 链表的解法总结#xff1a; 1 链表的知识点#xff1a;1 LC链表合集#xff1a;1.1 lc206反转链表#xff1a; 双指针#xff1a;lc25: K个一组翻转链表#xff1a;栈1.2 lc203移除链表元素#xff1a;1.3 设计链表#xff1a;1.4… 数据结构刷题-链表 总结1 链表的解法总结 1 链表的知识点1 LC链表合集1.1 lc206反转链表 双指针lc25: K个一组翻转链表栈1.2 lc203移除链表元素1.3 设计链表1.4 lc160相交链表: 双指针指针相遇1.5 lc2两个链表相加双指针lc 141环形链表双指针快慢指针龟兔赛跑lc142 环形链表2lc21 合并两个有序链表三指针lc19 删除链表的倒数第N个节点双指针快慢指针lc148 排序链表重点可以复习排序算法lc23 合并k个升序链表hard:lc146 LRU缓存 2 面试手撕-关于链表2.1 百度-模型工程2.2 虾皮笔试合并升序链表lc21:2.3 暑期字节一面阿里云暑期一面拼多多面试2.4 华为链表去重2.5 华为手撕删除链表倒数第n个节点2.6 字节跳动:找到两链表第一个公共节点翻转单链表判断链表是否有环 链表应该是面试时被提及最频繁的数据结构。链表的结构很简单它由指针把若干个节点连接乘链状结构。链表的常见插入节点删除节点等操作只需要20行左右代码就可以实现其代码量非常适合面试。所以这也是我面试百度的时候面试官上来就问我如何反转一个链表 以及如何以K组进行链表的反转所以lc hot100上面关于链表的题目基本上都要能背出来的水平。 总结 1 链表的解法总结
1双指针
比如翻转链表环形链表删除倒数第n个节点相交链表链表题目是把双指针发挥利用到极致的题目因为只能一步一步遍历没有办法。
2虚拟头结点合并有序链表虚拟头双指针
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了头结点的尴尬因为头结点没有前一个节点了。每次对应头结点的情况都要单独处理所以使用虚拟头结点的技巧就可以解决这个问题。
3排序问题排序算法
其实排序链表基本上就算是数组排序的变种吧感觉差别不是很大。 1 链表的知识点
链表是一个动态数据结构在创建链表时无须知道链表的长度。当插入一个节点时只需要为这个新节点分配内存然后调整指针指向就好了。 内存分配也不是在常见链表时一次性完成的而是每添加一个节点分配一次内存。 由于没有闲置内存所以链表的空间效率较高。单向链表的节点定义如下
Definition for singly-linked list.
class ListNode:def __init__(self, val0, nextNone):self.val valself.next next
由于链表中的内存不是一次性分配的因而我们在访问链表中第i个节点时只能从头开始按照指向去找到某个节点。感觉就跟走地图一样你只有先走到某个地方然后按照npc的指引才能到达目的地。而列表就相当于你已经把这些地方打通关了到时候要是想再来这个地方直接传送就好了。
要掌握链表的操作方式如何使用以及如何连接下一级值是值next是next;看你调用啥。一般来说如下面代码所示head不是一个列表形式的不能遍历的。只是一个节点本身具有值以及指向后面的值。比如下面这张图所示head只是开头的数字节点罢了。
也很简单那就是找到你想要输出顺序的头比如下面的代码最后输出的是pre因为pre就是指向性的头。这样的话代码会自动的输出整个链表的值。就是因为没有搞懂链表所以连输出都不会输出甚至连指向啥的也不会。
return dummy_head.next1 LC链表合集 1.1 lc206反转链表 双指针
给你单链表的头节点 head 请你反转链表并返回反转后的链表。解法1添加为无的pre 2暂存下一节点3反转4两个节点移动更新使用技法双指针 #Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution:def reverseList(self, head: ListNode) - ListNode:cur head pre None # 虚拟头未构建关联后面会构建指向while cur:next_node cur.next # 保存一下 cur的下一个节点因为接下来要改变cur-nextcur.next pre #反转#更新pre、cur指针pre curcur next_nodereturn prelc25: K个一组翻转链表栈
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。自己想了好几种解法都没有办法写出来但是看到一种解法感觉非常有意思。借助了栈的帮助把问题变的非常简单了。
class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]:# 双指针# 使用栈# 虚拟头# 如果不满足K的时候不翻转这个怎么做到的?直接返回h t dum ListNode(next head)p,stack head,[]while True:for _ in range(k):# 入栈if p:stack.append(p)p p.nextelse:# 输出return h.next# 出栈for _ in range(k):t.next stack.pop()t t.next#中间连接t.next p 1.2 lc203移除链表元素
果然自己写过的题目还是不会写。其原因在于没有深层次的搞明白。深层次的总结他们区别。内化成自己的东西。使用技法虚拟头虚拟头指向head避免第一个元素就要删除的麻烦。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]:# 使用虚拟头的方法# 每次检查当前值的下一个值是否为目标值如果为目标值则讲目标值的后面一个值变成下一个# 构建虚拟头, 构建关联dummy_head ListNode(next head)# 遍历curr dummy_headwhile curr.next:if curr.next.val val:curr.next curr.next.nextelse:curr curr.nextreturn dummy_head.next
时间复杂度: O(n)空间复杂度: O(1) 1.3 设计链表
通过设计链表感受到了链表是如何进行操作的。比如说虚拟头感觉这个虚拟头挺有用的。重点可以可能啊get这个里面想要得到某个值需要curr dummy_head.next,然后一步一步的走才能到第多少个难道不能像列表那样直接得到某个位置的值吗不可以直接得到因为内存不是连续的不知道下面一个是啥。
版本一单链表法
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass MyLinkedList:def __init__(self):self.dummy_head ListNode()self.size 0def get(self, index: int) - int:if index 0 or index self.size:return -1current self.dummy_head.nextfor i in range(index):current current.nextreturn current.valdef addAtHead(self, val: int) - None:self.dummy_head.next ListNode(val, self.dummy_head.next)self.size 1def addAtTail(self, val: int) - None:current self.dummy_headwhile current.next:current current.nextcurrent.next ListNode(val)self.size 1def addAtIndex(self, index: int, val: int) - None:if index 0 or index self.size:returncurrent self.dummy_headfor i in range(index):current current.nextcurrent.next ListNode(val, current.next)self.size 1def deleteAtIndex(self, index: int) - None:if index 0 or index self.size:returncurrent self.dummy_headfor i in range(index):current current.nextcurrent.next current.next.nextself.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.4 lc160相交链表: 双指针指针相遇
解法就是走路问题感觉跟脑筋急转弯一样。复杂度分析时间复杂度 O(ab) 最差情况下即 ∣a−b∣1 , c0 此时需遍历 ab个节点。空间复杂度 O(1) 节点指针 A , B 使用常数大小的额外空间。作者Krahets链接https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/12624/intersection-of-two-linked-lists-shuang-zhi-zhen-l/
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]:# 怎么感觉1也那么像呢怎么判断的呢# 看了题解就明白了两个链表相交的点# 就是a走一步b走一步 a走完自己去走b,b走完自己去走a;他们第二次相遇的地方就是重合的地方因为走的距离是一样的# 也算是双指针a ,b headA,headBwhile a ! b:if a:a a.nextelse:a headBif b:b b.nextelse:b headAreturn a1.5 lc2两个链表相加双指针
自己的解法超时了确实太冗余了其实本身把各位放在前面就是为了方便你进位的自己的这种想法太垃圾了太慢了应该把计算进位一起放到求和里面
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:# 1先读取然后数字再相加然后再生成链表def get_num(list_node):num 0res 0while list_node:res list_node.val*(10**num) resnum 1return resnum1 get_num(l1)num2 get_num(l2)num num1 num2# 构建反向列表以虚拟头0为开头dummy_node ListNode(0)prev dummy_nodewhile num 0:prev.next num%10# 更新num num//10prev prev.nextreturn dummy_node.next
按照自己的想法写了一个版本但是还是不对超时了不知道什么情况。而且他的这种写法非常Nb,通过or判断判断进位是否用完了。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:# 1依次读取相加进位# 新建一个从0开始的虚拟头dummy_node ListNode(0)cur dummy_nodenum_jin 0while l1 or l2 or num_jin:# 需要加上一些判断因为l1和l2长度不一样num_jin (l1.val if l1 else 0) (l2.val if l2 else 0) num_jincur.next ListNode(num_jin%10)num_jin // 10cur cur.next# 记得更新if l1 :l1 l1.nextif l2:l2 l2.nextreturn dummy_node.nextlc 141环形链表双指针快慢指针龟兔赛跑
给你一个链表的头节点 head 判断链表中是否有环。解法
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) - bool:# 龟兔赛跑fast headslow head# 如果fast的下面一个值没有值while fast and fast.next:fast fast.next.nextslow slow.nextif fast slow:return Truereturn Falselc142 环形链表2
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。考察两个知识点1有无环2环的开头有无环使用快慢指针环的开头需要推导解法1; 快慢指针
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:# 首先是判断有环使用龟兔赛跑# 然后是判断环的入口使用乌龟的路径 # 使用龟兔的双指针是可以的但是感觉推导非常的繁琐# 虽然可以使用哈希表的方法但是假如遇到那种节点相同的元素可能就不怎么适用了# 使用快慢指针的公式推导fast,slow head,headwhile fast and fast.next:fast fast.next.nextslow slow.nextif fast slow:slow headwhile slow ! fast:slow slow.nextfastfast.nextreturn fastreturn None解法2哈希表但是感觉不鲁棒 如果遇到相同的数字就直接G了。
class Solution(object): def detectCycle(self, head): a head dic {} while a: if a in dic: return a dic[a] True # 这里只需要一个标记不需要具体的值 a a.next return Nonelc21 合并两个有序链表三指针
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 相当于三指针两个指针进行比较一个指针进行构建重点在于构建虚拟头prehead Listnode(0);
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]:# 通过比较来构建指向# 双指针# 需要在最前面构建一个节点这个节点方便构建整个链表# 构建这个prehead也是为了方便输出prehead ListNode(0) # prev preheadwhile list1 and list2:# 对比 1和2if list1.val list2.val:prev.next list1# 更新list1 list1.nextelse:prev.next list2# list2 list2.next# prev也要动,更新prev prev.next# 某个链表里面还剩下一个prev.next list1 if list1 else list2return prehead.nextlc19 删除链表的倒数第N个节点双指针快慢指针
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。解法删除链表中某个节点简单但是因为链表中没有节点数量这一说。 怎么去对链表的节点数量进行计数呢 而且是倒数第N个节点。下面是我的想法是先利用列表来进行计算但是感觉太繁琐了使用了两次遍历
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:# 可以使用栈吗使用栈还不如使用列表吗# 加入列表计数# 需要加上虚拟头为了防止只有一个数的cur headlist1 []while cur:list1.append(cur.val)cur cur.nextif len(list1) 1:return Nonel len(list1)-n# 需要加上虚拟头为了防止只有一个数的dum ListNode(next head)cur dumcount 0while cur and cur.next:if count l:cur.next cur.next.nextelse:cur cur.nextcount 1return dum.next
双指针快慢指针法快指针先走n步
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:# 双指针快慢指针# 需要加上虚拟头为了防止只有一个数的dum ListNode(nexthead)fast slow dum# 快指针先走for _ in range(n1):fast fast.next # 然后一起走当fast为空slow也到了while fast:fast fast.nextslow slow.next# 然后删除slow.next slow.next.nextreturn dum.nextlc148 排序链表重点可以复习排序算法
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。解法作者ITCharge链接https://leetcode.cn/problems/sort-list/solutions/1785874/by-itcharge-01zg/
可以参考数据排序的知识点。在数组排序中常见的排序算法有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。而对于链表排序而言因为链表不支持随机访问访问链表后面的节点只能依靠 next 指针从头部顺序遍历所以相对于数组排序问题来说链表排序问题会更加复杂一点。下面先来总结一下适合链表排序与不适合链表排序的算法
适合链表的排序算法冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。不适合链表的排序算法希尔排序。可以用于链表排序但不建议使用的排序算法堆排序。
希尔排序为什么不适合链表排序希尔排序希尔排序中经常涉及到对序列中第 i gap 的元素进行操作其中 gap 是希尔排序中当前的步长。而链表不支持随机访问的特性导致这种操作不适合链表因而希尔排序算法不适合进行链表排序。
为什么不建议使用堆排序堆排序堆排序所使用的最大堆 / 最小堆结构本质上是一棵完全二叉树。而完全二叉树适合采用顺序存储结构数组。因为数组存储的完全二叉树可以很方便的通过下标序号来确定父亲节点和孩子节点并且可以极大限度的节省存储空间。而链表用在存储完全二叉树的时候因为不支持随机访问的特性导致其寻找子节点和父亲节点会比较耗时如果增加指向父亲节点的变量又会浪费大量存储空间。所以堆排序算法不适合进行链表排序。如果一定要对链表进行堆排序则可以使用额外的数组空间表示堆结构。然后将链表中各个节点的值依次添加入堆结构中对数组进行堆排序。排序后再按照堆中元素顺序依次建立链表节点构建新的链表并返回新链表头节点。
需要用到额外的辅助空间进行排序的算法刚才我们说到如果一定要对链表进行堆排序则需要使用额外的数组空间。除此之外计数排序、桶排序、基数排序都需要用到额外的数组空间。接下来我们将对适合链表排序的 8 种算法进行一一讲解。当然这些排序算法不用完全掌握重点是掌握 「链表插入排序」、「链表归并排序」 这两种排序算法。
**思路1**链表冒泡排序超时让我学到的是竟然可以直接就像数组一样直接交换节点的数值好像并没有改变指向性。
class Solution:def bubbleSort(self, head: ListNode):node_i headtail None# 外层循环次数为 链表节点个数while node_i:node_j headwhile node_j and node_j.next ! tail:if node_j.val node_j.next.val:# 交换两个节点的值node_j.val, node_j.next.val node_j.next.val, node_j.valnode_j node_j.next# 尾指针向前移动 1 位此时尾指针右侧为排好序的链表tail node_jnode_i node_i.nextreturn headdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.bubbleSort(head)时间复杂度O(n^2)空间复杂度O(1)
思路2链表选择排序超时每次找最小值然后放在前面
class Solution:def sectionSort(self, head: ListNode):node_i head# node_i 为当前未排序链表的第一个链节点while node_i and node_i.next:# min_node 为未排序链表中的值最小节点min_node node_inode_j node_i.nextwhile node_j:if node_j.val min_node.val:min_node node_jnode_j node_j.next# 交换值最小节点与未排序链表中第一个节点的值if node_i ! min_node:node_i.val, min_node.val min_node.val, node_i.valnode_i node_i.nextreturn headdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.sectionSort(head)时间复杂度O(n^2)空间复杂度O(1)
思路3链表插入排序超时创建一个新的链表然后一个一个通过比较插入进去。
class Solution:def insertionSort(self, head: ListNode):if not head or not head.next:return headdummy_head ListNode(-1)dummy_head.next headsorted_list headcur head.next while cur:if sorted_list.val cur.val:# 将 cur 插入到 sorted_list 之后sorted_list sorted_list.next else:prev dummy_headwhile prev.next.val cur.val:prev prev.next# 将 cur 到链表中间sorted_list.next cur.nextcur.next prev.nextprev.next curcur sorted_list.next return dummy_head.nextdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:return self.insertionSort(head)时间复杂度O(n^2)空间复杂度O(1)
思路4链表归并排序通过题目要求时间空间复杂度分别为 O(nlogn) 和 O(1)根据时间复杂度我们自然想到二分法从而联想到归并排序通过递归实现链表归并排序有以下两个环节
class Solution:def sortList(self, head: ListNode) - ListNode:if not head or not head.next: return head # termination.# cut the LinkedList at the mid index.slow, fast head, head.nextwhile fast and fast.next:fast, slow fast.next.next, slow.nextmid, slow.next slow.next, None # save and cut.# recursive for cutting.left, right self.sortList(head), self.sortList(mid)# merge left and right linked list and return it.h res ListNode(0)while left and right:if left.val right.val: h.next, left left, left.nextelse: h.next, right right, right.nexth h.nexth.next left if left else rightreturn res.next作者Krahets
链接https://leetcode.cn/problems/sort-list/solutions/13728/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。思路5链表快速排序超时感觉这些算法很多只要你把数组上的理解了放到链表上也不是问题。从链表中找到一个基准值 pivot这里以头节点为基准值。然后通过快慢指针 node_i、node_j 在链表中移动使得 node_i 之前的节点值都小于基准值node_i 之后的节点值都大于基准值。从而把数组拆分为左右两个部分。再对左右两个部分分别重复第二步直到各个部分只有一个节点则排序结束。注意虽然链表快速排序算法的平均时间复杂度为 O(n×log2n)。但链表快速排序算法中基准值 pivot 的取值做不到数组快速排序算法中的随机选择。一旦给定数据是有序链表时间复杂度就会退化到O(n^2)。这也是这道题目使用链表快速排序容易超时的原因。
class Solution:def partition(self, left: ListNode, right: ListNode):# 左闭右开区间没有元素或者只有一个元素直接返回第一个节点if left right or left.next right:return left# 选择头节点为基准节点pivot left.val# 使用 node_i, node_j 双指针保证 node_i 之前的节点值都小于基准节点值node_i 与 node_j 之间的节点值都大于等于基准节点值node_i, node_j left, left.nextwhile node_j ! right:# 发现一个小与基准值的元素if node_j.val pivot:# 因为 node_i 之前节点都小于基准值所以先将 node_i 向右移动一位此时 node_i 节点值大于等于基准节点值node_i node_i.next# 将小于基准值的元素 node_j 与当前 node_i 换位换位后可以保证 node_i 之前的节点都小于基准节点值node_i.val, node_j.val node_j.val, node_i.valnode_j node_j.next# 将基准节点放到正确位置上node_i.val, left.val left.val, node_i.valreturn node_idef quickSort(self, left: ListNode, right: ListNode):if left right or left.next right:return leftpi self.partition(left, right)self.quickSort(left, pi)self.quickSort(pi.next, right)return leftdef sortList(self, head: Optional[ListNode]) - Optional[ListNode]:if not head or not head.next:return headreturn self.quickSort(head, None) lc23 合并k个升序链表hard:
给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。解法思路1两两合并 time16%我知道如何合并如何合并两个那三个是不是一样?重点注意在两两合并时不要忽略当l1或l2某一个已经完成之后另外一个还没完成要接上去。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]:# 两个可以合并三个是不是调用两个的函数就ok了# 合并两个def merge_two(list1,list2):dum ListNode(0)cur dumwhile list1 and list2:if list1.val list2.val:cur.next list1list1 list1.nextelse:cur.next list2list2 list2.nextcur cur.next# 连接后续非空链表cur.next list1 if list1 else list2return dum.nextif not lists:return Noneres lists[0]for i in range(len(lists)-1):res merge_two(res,lists[i1])return res
思路2归并排序time60%最后的两链表合并部分不变上部的两两合并改成归并形式的递归操作。
class Solution:def mergeKLists(self, lists: List[ListNode]) - ListNode:if not lists: return Nonen len(lists) #记录子链表数量return self.mergeSort(lists, 0, n - 1) #调用归并排序函数def mergeSort(self, lists: List[ListNode], l: int, r: int) - ListNode:if l r:return lists[l]m (l r) // 2L self.mergeSort(lists, l, m) #循环的递归部分R self.mergeSort(lists, m 1, r)return self.mergeTwoLists(L, R) #调用两链表合并函数def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode:dummy ListNode(0) #构造虚节点move dummy #设置移动节点等于虚节点while l1 and l2: #都不空时if l1.val l2.val:move.next l1 #移动节点指向数小的链表l1 l1.nextelse:move.next l2l2 l2.nextmove move.nextmove.next l1 if l1 else l2 #连接后续非空链表return dummy.next #虚节点仍在开头思路3最小堆 time90%利用堆的数据结构可以极大地简化代码。
class Solution:def mergeKLists(self, lists: List[ListNode]) - ListNode:import heapq #调用堆minHeap []for listi in lists: while listi:heapq.heappush(minHeap, listi.val) #把listi中的数据逐个加到堆中listi listi.nextdummy ListNode(0) #构造虚节点p dummywhile minHeap:p.next ListNode(heapq.heappop(minHeap)) #依次弹出最小堆的数据p p.nextreturn dummy.next lc146 LRU缓存
没看懂感觉应该也不会考这种题目。 class Node:# 提高访问属性的速度并节省内存__slots__ prev, next, key, valuedef __init__(self, key0, value0):self.key keyself.value valueclass LRUCache:def __init__(self, capacity: int):self.capacity capacityself.dummy Node() # 哨兵节点self.dummy.prev self.dummyself.dummy.next self.dummyself.key_to_node dict()def get_node(self, key: int) - Optional[Node]:if key not in self.key_to_node: # 没有这本书return Nonenode self.key_to_node[key] # 有这本书self.remove(node) # 把这本书抽出来self.push_front(node) # 放在最上面return nodedef get(self, key: int) - int:node self.get_node(key)return node.value if node else -1def put(self, key: int, value: int) - None:node self.get_node(key)if node: # 有这本书node.value value # 更新 valuereturnself.key_to_node[key] node Node(key, value) # 新书self.push_front(node) # 放在最上面if len(self.key_to_node) self.capacity: # 书太多了back_node self.dummy.prevdel self.key_to_node[back_node.key]self.remove(back_node) # 去掉最后一本书# 删除一个节点抽出一本书def remove(self, x: Node) - None:x.prev.next x.nextx.next.prev x.prev# 在链表头添加一个节点把一本书放在最上面def push_front(self, x: Node) - None:x.prev self.dummyx.next self.dummy.nextx.prev.next xx.next.prev x作者灵茶山艾府
链接https://leetcode.cn/problems/lru-cache/solutions/2456294/tu-jie-yi-zhang-tu-miao-dong-lrupythonja-czgt/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。2 面试手撕-关于链表 2.1 百度-模型工程
问题请你反转链表 请你以K为一组反转链表注意要自己定义链表类翻转链表双指针以K为一组翻转链表 使用栈 2.2 虾皮笔试合并升序链表lc21:
这个比较简单参考lc21;k可以说是使用三指针注意合并的时候某一个还剩下的尾巴。 2.3 暑期字节一面阿里云暑期一面拼多多面试
要求要有优化合并K个升序链表原题请看lc23,可以两两合并也可以使用归并-递归的方式。 2.4 华为链表去重 2.5 华为手撕删除链表倒数第n个节点 2.6 字节跳动:找到两链表第一个公共节点翻转单链表判断链表是否有环
