链表

旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 首先判断头节点是不是为空，或者整个链表只有一个节点
        if not head or not head.next:
            return head

        # 计算链表长度
        cur = head
        count = 1
        while cur.next:
            count += 1
            cur = cur.next

        # 首尾相连
        cur.next = head

        # 从count-k处断开连接
        k = k % count
        cur = head
        for _ in range(count - k - 1):
            cur = cur.next

        res = cur.next
        cur.next = None

        return res

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) 的平均时间复杂度运行。