力扣（python3)2026.4.3自用

138.随机链表的复制给你一个长度为n的链表每个节点包含一个额外增加的随机指针random该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。 深拷贝应该正好由n个全新节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。例如如果原链表中有X和Y两个节点其中X.random -- Y。那么在复制链表中对应的两个节点x和y同样有x.random -- y。返回复制链表的头节点。用一个由n个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示val一个表示Node.val的整数。random_index随机指针指向的节点索引范围从0到n-1如果不指向任何节点则为null。你的代码只接受原链表的头节点head作为传入参数。思路 今天做的题都没有什么思路可能第一次见有思路也不对。进展有点慢这个题如果没有random这个指针的话只有next那只需要边构建节点边复制val 然后连接到新的链表上就可以了。但是有random的话它的指向是随机的它指向的节点可能目前构造不出来。正解将原链表的节点和新链表的节点用哈希表做一个映射。这样 .next和 random都可以通过这个哈希表来完成。需要注意dct.get()这个函数意思是没有这个key 就会返回None # Definition for a Node. class Node: def __init__(self, x: int, next: Node None, random: Node None): self.val int(x) self.next next self.random random class Solution: def copyRandomList(self, head: Optional[Node]) - Optional[Node]: if head None: return None # 旧节点和新节点做映射构造哈希保证新节点的指针指向的都是新节点 cur head dct {} while cur: dct[cur] Node(cur.val) cur cur.next # 怎么把新节点都连接起来 cur head while cur: dct[cur].next dct.get(cur.next) dct[cur].random dct.get(cur.random) cur cur.next return dct[head]148.排序链表给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3]输出[1,2,3,4]思路这个题要求时间复杂度为O(NlogN) 。关于排序问题时间复杂度小的就是 归并排序快排和堆排。这个题用归并排序。那就需要把链表从中间断开处理然后不断递归。递归的过程是不断断开的过程最后需要一次总的合并。从中间断开需要快慢指针。# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: # 时间复杂度很低的话排序有归并快排和堆排 # 这个题用归并先利用快慢指针把链表分成2份然后每份自己排这个就是递归的过程。最后利用合并两个有序链表合并起来 if not head or head.next None: return head slow head fast head.next while fast and fast.next: slow slow.next fast fast.next.next mid slow.next slow.next None left self.sortList(head) #因为slow指针已经把链表分开了 right self.sortList(mid) return self.mergeList(left,right) def mergeList(self,left:ListNode,right:ListNode): dummy ListNode(-1) tmp dummy l left r right while l and r: if l.val r.val: tmp.next l l l.next else: tmp.next r r r.next tmp tmp.next tmp.next l if l else r return dummy.next23.合并K个升序链表给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。示例 1输入lists [[1,4,5],[1,3,4],[2,6]]输出[1,1,2,3,4,4,5,6]解释链表数组如下 [ 1-4-5, 1-3-4, 2-6 ] 将它们合并到一个有序链表中得到。 1-1-2-3-4-4-5-6思路这个题和上面题类似。分治思想两两合并得到一个升序链表然后再两两合并最后合并为一个升序链表。需要一个递归函数不断处理从中间断开的过程然后最后进行一次合并# 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]: # 合并所有的总合并 if not lists: return None l 0 r len(lists) - 1 return self.merge(lists,l,r) def merge(self,lists,l,r): if l r: return lists[l] mid (l r) //2 left self.merge(lists,l,mid) right self.merge(lists,mid 1,r) return self.mergeTwolists(left,right) def mergeTwolists(self,left,right): dummy ListNode(-1) cur dummy while left and right: if left.val right.val: cur.next left left left.next else: cur.next right right right.next cur cur.next cur.next left if left else right return dummy.next146.LRU缓存请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现LRUCache类LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中则返回关键字的值否则返回-1。void put(int key, int value)如果关键字key已经存在则变更其数据值value如果不存在则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字。函数get和put必须以O(1)的平均时间复杂度运行。示例输入[LRUCache, put, put, get, put, get, put, get, get, get] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]输出[null, null, null, 1, null, -1, null, -1, 3, 4]解释LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4思路这个题看到之后没想法看答案是哈希表 双向链表。正解 哈希表用来存储 key和节点的映射方便快速查找是否存在这个节点双向链表用来快速的删除和添加节点。需要定义head 和tail 节点head之后的节点为最新使用的tail之前的节点为最久不使用的。# 哈希表 双向链表哈希表映射key和节点这样可以快速判断存不存在 # 双向链表可以快速删除和增加节点 # 1、定义双向链表 # 2、定义head和tail节点head之后的节点为最新操作过的tail前节点为最久不使用的 class DlinkListNode: def __init__(self,key 0,value 0): self.key key self.value value self.next None self.prev None class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.head DlinkListNode() self.tail DlinkListNode() self.head.next self.tail self.tail.prev self.head self.mp {} # key和节点的映射 def move(self,node): node.next self.head.next self.head.next.prev node self.head.next node node.prev self.head def dele(self,node): node.prev.next node.next node.next.prev node.prev def get(self, key: int) - int: # 判断当前在不在哈希表在返回value并移到head后面还需要再当前位置删除节点。不在返回-1 # 定义移动到head后面的函数方便复用 if key in self.mp: self.dele(self.mp[key]) self.move(self.mp[key]) return self.mp[key].value return -1 def put(self, key: int, value: int) - None: # 判断当前是否存在 if key in self.mp: self.mp[key].value value self.dele(self.mp[key]) self.move(self.mp[key]) else: node DlinkListNode(key,value) self.move(node) self.mp[key] node if len(self.mp) self.capacity: tail_prev self.tail.prev self.dele(tail_prev) del self.mp[tail_prev.key] # Your LRUCache object will be instantiated and called as such: # obj LRUCache(capacity) # param_1 obj.get(key) # obj.put(key,value)