16. Linked list

A. General Introduction

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”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [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:

Image from https://leetcode.com/problems/add-two-numbers/

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