# 16. Linked list

## B. Leetcode Problems

### 146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example:

Input:
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[, [1, 1], [2, 2], , [3, 3], , [4, 4], , , ] \

Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

#### Key Ideas

• Use a hashmap to store the key and corresponding node in the doubly linked list.
• Use a two pointers left and right to point to the head and tail of the doubly linked list.
• left pointer is the least recently used node, right pointer is the most recently used node.
• When get a node, move the node to the right of the doubly linked list.
• When put a node, if the node already exists, move the node to the right of the doubly linked list Otherwise, add the node to the right of the doubly linked list.
• When the hashmap reaches capacity, remove the node pointed by the left pointer.
Code


class Node:

def __init__(self, k:int, v:int, prv:"Node"=None, nxt:"Node"=None):

self.key = k
self.val = v
self.prev = prv
self.next = nxt

class LRUCache:

def __init__(self, capacity: int):
"""Initialize a capacity, left and right pointer"""

self.cap = capacity

self.l = Node(0,0) # Least recently used node
self.r = Node(0,0) # Most recently used node

self.l.next, self.r.prev = self.r, self.l

self.cache = {}

def remove(self, node: Node) -> None:

prv, nxt = node.prev, node.next
prv.next, nxt.prev = nxt, prv

def append(self, node: Node) -> None:

next_node = self.r.prev
next_node.next, node.prev = node, next_node

self.r.prev, node.next = node, self.r

def get(self, key: int) -> int:

if key not in self.cache:
return -1

node = self.cache[key]
val = node.val

self.remove(node)
self.append(node)

return val

def put(self, key: int, value: int) -> None:

if key in self.cache:
self.remove(self.cache[key])

node = Node(key, value)
self.cache[key] = node
self.append(node)

if len(self.cache) > self.cap:
lru_node = self.l.next
self.remove(lru_node)
del self.cache[lru_node.key]

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)



### 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

#### Key Ideas

• Use a dummy node to store the head of the linked list.
• Use a carry variable to store the carry of the addition.
• Run the loop till l1 or l2 are not None or carry is not 0.
• Add the values of l1 and l2 and carry and store the sum in sum.
• Create a new node with sum % 10 as the value.
• Update the carry to sum // 10.
Code


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

dummy = ListNode()
current = dummy

carry = 0

while l1 or l2 or carry:

v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0

res = v1+v2+carry

val = res % 10
carry = res//10

current.val = val

l1 = l1.next if l1 else None
l2 = l2.next if l2 else None

if l1 or l2 or carry:
current.next = ListNode()
current = current.next

return dummy



Previous
Next