力扣（python3)2026.4.3自用

m0_68478087

419人浏览 · 2026-04-03 17:53:06

m0_68478087 · 2026-04-03 17:53:06 发布

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, val=0, next=None):
#         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.next

23.合并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, val=0, next=None):
#         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.next

146.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); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
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)