Linked List Flashcards
- Reverse Linked List
Solved
Easy
Topics
Companies
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
https://leetcode.com/problems/reverse-linked-list/description/
class ListNode:
Definition for singly-linked list.
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
prev = None
temp = None
while cur:
temp, cur.next = cur.next, prev
prev, cur = cur, temp
return prev
"""
:type head: ListNode
:rtype: ListNode
"""
prev = None
cur = head
while(cur):
t = cur.next
cur.next, prev = prev, cur
cur = t
return prev
Definition for singly-linked list.
# class ListNode(object):
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
if not head:
return None
if not head.next:
return head
h = self.reverseList(head.next)
temp = head.next.next
head.next.next = head
head.next = temp
return h
- Merge Two Sorted Lists
Solved
Easy
Topics
Companies Facebook
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.
https://leetcode.com/problems/merge-two-sorted-lists/
class ListNode:
Definition for singly-linked list.
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur_a, cur_b = list1, list2
ret = ListNode()
cur_ret = ret
while cur_a and cur_b:
if cur_a.val >= cur_b.val:
temp = cur_b
cur_b = cur_b.next
temp.next = None
else:
temp = cur_a
cur_a = cur_a.next
temp.next = None
cur_ret.next = temp
cur_ret = cur_ret.next
if cur_a:
cur_ret.next = cur_a
elif cur_b:
cur_ret.next = cur_b
return ret.next
Solved
Medium
Topics
Companies
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
The number of nodes in the list is in the range [1, 5 * 104].
1 <= Node.val <= 1000
https://leetcode.com/problems/reorder-list/description/
class ListNode:
# Definition for singly-linked list.
# class ListNode(object):
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
# One Pass Recursion
def rec(head, runner):
if not runner.next:
return head
nx_head = rec(head, runner.next)
# Runner will be none when any of the next two cases are met.
# nx_head.next will be none if nodes are odd numbered
# runner will be equal to nx_head when nodes are equal numbered.
# The logic works as follows
# 1,2,3,4
# 1 -> 4 -> 2 (runner = 3, nx_head = 1) (Set runner.next = None, ie. 3->None)
# 1 -> 4 -> 2 -> 3 -> None (runner = 2, nx_head = 2 << runner = nx_head, runner.next = None)
# Odd, 1,2,3
# 1 -> 3 -> 2 (runner = 2, nx_head = 2) (set runner.next = None)
# 1 -> 3 -> 2 -> None (runner = 1, nx_head = 2, << nx_head.next == None )
if not nx_head or not nx_head.next or nx_head == runner:
return None
# Save these 2 temp variables
nxt_node = runner.next
nx_nx_head = nx_head.next
nx_head.next = nxt_node
runner.next = None # we do not need it anymore, this is to have a clean ending list, otherwise cycles
nx_head.next.next = nx_nx_head
return nx_nx_head
rec(head, head)
Interleave using splitting list in middle
~~~
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
“””
Do not return anything, modify head in-place instead.
“””
# Other way, reach center, reverse the list, interleave join them
# reach center
fast, slow = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Slow is at the center now
#Reverse from slow onwards
prev = None
cur = slow
while cur:
cur.next, cur, prev = prev, cur.next, cur
# prev is the head of the reversed list now interleave join them
second = prev
first = head
while second.next:
first.next, second.next, first, second = second, first.next, first.next, second.next ~~~
O(n), space O(1)
- Remove Nth Node From End of List
Solved
Medium
Topics
Companies Facebook Amazon
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
Constraints:
The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
Follow up: Could you do this in one pass?
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
class ListNode:
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
def remove(runner):
if not runner:
return 1, None
this_n, runner.next = remove(runner.next)
if this_n == n:
return this_n+1, runner.next
else:
return this_n+1, runner
return remove(head)[1]
Another way
Definition for singly-linked list.
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
def rec(h, n):
if not h.next:
return 1
pos = rec(h.next, n)
if pos != n:
return pos + 1
else:
h.next = h.next.next
return pos + 1
rechead = head
out = rec(rechead, n)
return head if out > n else head.next
- Copy List with Random Pointer
Medium
Topics
Companies Facebook
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Constraints:
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random is null or is pointing to some node in the linked list.
https://leetcode.com/problems/copy-list-with-random-pointer/description/
Definition for a Node.
"""
class Node:
def \_\_init\_\_(self, x, next=None, random=None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
nodemap = {}
sentinel = Node(-1)
ret = sentinel
cur = head
while cur:
this_node = None
if cur in nodemap:
this_node = nodemap[cur]
else:
this_node = Node(cur.val)
nodemap[cur] = this_node
this_random = None
cur_random = cur.random
if cur_random and not this_node.random:
if cur_random in nodemap:
this_random = nodemap[cur_random]
else:
this_random = Node(cur_random.val)
nodemap[cur_random] = this_random
this_node.random = this_random
ret.next = this_node
ret = ret.next
cur = cur.next
return sentinel.next
- Reverse Linked List II
Solved
Medium
Topics
Companies
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
Constraints:
The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
Follow up: Could you do it in one pass?
https://leetcode.com/problems/reverse-linked-list-ii/?envType=study-plan-v2&envId=top-interview-150
then reverse the list till the right count.
key is to keep the node before the start saved somewhere.
NeetCode Solution
Empty list
~~~
class Solution:
def reverseBetween(self, head, m, n):
“””
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
“””
if not head:
return None
prev, cur = None, head
while m > 1:
prev = cur
cur = cur.next
m, n = m-1, n-1
tail, con = cur, prev
while n:
third = cur.next
cur.next = prev
prev = cur
cur = third
n -= 1
if con:
con.next = prev
else:
head = prev
tail.next = cur
return head ~~~
The Solution bellow just does it in one main loop, just slightly different than the first one, i think easier to understand. It just does a simple reverse once we find the m-1’th node.
class Solution:
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
count = 0
sentinel = ListNode()
sentinel.next = head
cur = sentinel
start = None
while cur and count <= n:
if count < m:
start = cur
cur = cur.next
count += 1
else:
prev = None
tail = cur
while count <= n and cur:
cur.next, prev, cur = prev, cur, cur.next
count += 1
start.next = prev
tail.next = cur
return sentinel.next
O(n), Space: O(1)
- Add Two Numbers
Solved
Medium
Topics
Companies
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 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
https://leetcode.com/problems/add-two-numbers
class ListNode:
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()
cur = dummy
carry = 0
curA = l1
curB = l2
while curA or curB:
vala = curA.val if curA else 0
valb = curB.val if curB else 0
total = vala + valb + carry
carry = total // 10
val = total % 10
node = ListNode(val)
cur.next = node
cur = cur.next
curA = curA.next if curA else None
curB = curB.next if curB else None
if carry > 0:
node = ListNode(carry)
cur.next = node
cur = cur.next
return dummy.next
- Add Two Numbers II
Solved
Medium
Topics
Companies
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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 1:
Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
Example 2:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]
Example 3:
Input: l1 = [0], l2 = [0]
Output: [0]
Constraints:
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
Follow up: Could you solve it without reversing the input lists?
https://leetcode.com/problems/add-two-numbers-ii/description/
# 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]:
def getListLen(node):
l = 0
while node:
node = node.next
l += 1
return l
l1_len = getListLen(l1)
l2_len = getListLen(l2)
curl1 = l1
curl2 = l2
dummy = ListNode()
while l2_len > l1_len:
dummy.next = curl1
curl1 = dummy
dummy = ListNode()
l2_len -= 1
while l1_len > l2_len:
dummy.next = curl2
curl2 = dummy
dummy = ListNode()
l1_len -= 1
def add(l1node, l2node):
if not l1node and not l2node:
return None, 0
next_node, carry = add(l1node.next, l2node.next)
addn = l1node.val + l2node.val + carry
digit = addn%10
carry = addn//10
new_node = ListNode(digit, next_node)
return new_node, carry
head, carry = add(curl1, curl2)
if carry:
head = ListNode(carry, head)
return head
2
- Reverse Nodes in k-Group
Solved
Hard
Topics
Companies
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list’s nodes, only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Constraints:
The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1) extra memory space?
https://leetcode.com/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-interview-150
class ListNode(object):
# Definition for singly-linked list.
# class ListNode(object):
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
count = 0
cur = head
while cur:
count += 1
cur = cur.next
cur = head
sentinel = ListNode()
prev_tail = sentinel #dummy tail of previous swap
swaps = count // k
while swaps:
tail = cur
prev = None
for _ in range(k):
prev, cur.next, cur = cur, prev, cur.next
prev_tail.next = prev # the previous tail points to the swapped lists head.
prev_tail = tail # current tail now becomes previous tail
swaps -= 1
prev_tail.next = cur
return sentinel.next
O(n), space O(1)
- Merge k Sorted Lists
Solved
Hard
Topics
Companies
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.
https://leetcode.com/problems/merge-k-sorted-lists/description/
class ListNode:
The following solution uses heap to keep track of next node to add.
We fill the heap with the first value of each list to init.
Then as we remove value from heap, we add the next value from the list we removed the value from if it still has members.
O(k) for adding first k nodesO(log(k) for adding each node, we go over all nodes. O(nLog(k)) where n is the total nodes in all lists combined.
Space: O(k)
# 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]:
sentinel = ListNode()
cur = sentinel
heap = []
for i in range(len(lists)):
if lists[i]:
heapq.heappush(heap, (lists[i].val, i))
while heap:
_, idx = heapq.heappop(heap)
cur.next = lists[idx]
lists[idx] = lists[idx].next
cur = cur.next
if lists[idx]:
heapq.heappush(heap, (lists[idx].val, idx))
return sentinel.next
The following solution uses divide and conquer, keep splitting the list in the middle till only 2 or one list is left in a half, merge and return. Like Merge Sort
Time Complexity: O(nLog(k)) because we split the set in 2 each time, so we never have to compare k nodes just 2 at a time.
Space: O(Log(k)) , the stack size basically
~~~
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeKLists(self, lists):
“””
:type lists: List[ListNode]
:rtype: ListNode
“””
if not lists:
return None
elif len(lists) == 2:
return self.merge2(lists[0], lists[1])
elif len(lists) == 1:
return lists[0]
mid = len(lists)//2
m1, m2 = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
merged = self.merge2(m1, m2)
return merged
def merge2(self, list_a, list_b):
if not list_a:
return list_b
if not list_b:
return list_a
ctr_a = list_a
ctr_b = list_b
ret = ListNode()
ret_cur = ret
while (ctr_a and ctr_b):
if ctr_a.val <= ctr_b.val:
ret_cur.next = ctr_a
ctr_a = ctr_a.next
else:
ret_cur.next = ctr_b
ctr_b = ctr_b.next
ret_cur = ret_cur.next
if ctr_a:
ret_cur.next = ctr_a
elif ctr_b:
ret_cur.next = ctr_b
return ret.next ~~~
O(nLog(k)), Space: Log(k)
- Insert into a Sorted Circular Linked List
Medium
Companies: Facebook 2024
Given a Circular Linked List node, which is sorted in non-descending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.
If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.
If the list is empty (i.e., the given node is null), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the originally given node.
Example 1:
Input: head = [3,4,1], insertVal = 2
Output: [3,4,1,2]
Explanation: In the figure above, there is a sorted circular list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list. The new node should be inserted between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.
Example 2:
Input: head = [], insertVal = 1
Output: [1]
Explanation: The list is empty (given head is null). We create a new single circular list and return the reference to that single node.
Example 3:
Input: head = [1], insertVal = 0
Output: [1,0]
Constraints:
The number of nodes in the list is in the range [0, 5 * 104]. -106 <= Node.val, insertVal <= 106
10-15 mins
https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/description/
Definition for a Node.
We handle the following cases:
1. The insertVal lies between 2 nodes
2. We reach the inflection point (eg. reaching 3 in 312) and the insertVal is either greater/eq than current (true tail) or smaller/eq than the next (true head)
If we do not hit either of these cases before we have reached starting point, then the list has all same elements, in which case we can insert anywhere.
"""
class Node:
def \_\_init\_\_(self, val=None, next=None):
self.val = val
self.next = next
"""
class Solution:
def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
if not head:
ret = Node(insertVal)
ret.next = ret
return ret
cur = head
insertNode = Node(insertVal)
while cur.next!=head:
if cur.val <= insertVal <= cur.next.val:
break
if cur.val > cur.next.val and (insertVal <= cur.next.val or insertVal >= cur.val):
break
cur = cur.next
cur.next, insertNode.next = insertNode, cur.next
return head
O(n), O(1) space
- Remove Duplicates From an Unsorted Linked List
Medium
Companies: Goldman.S
Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values.
Return the linked list after the deletions.
Example 1:
Input: head = [1,2,3,2]
Output: [1,3]
Explanation: 2 appears twice in the linked list, so all 2’s should be deleted. After deleting all 2’s, we are left with [1,3].
Example 2:
Input: head = [2,1,1,2]
Output: []
Explanation: 2 and 1 both appear twice. All the elements should be deleted.
Example 3:
Input: head = [3,2,2,1,3,2,4]
Output: [1,4]
Explanation: 3 appears twice and 2 appears three times. After deleting all 3’s and 2’s, we are left with [1,4].
Constraints:
The number of nodes in the list is in the range [1, 105] 1 <= Node.val <= 105
10 mins
https://leetcode.com/problems/remove-duplicates-from-an-unsorted-linked-list/description/
key is to not move prev if deleting the node in the second pass.
~~~
from collections import defaultdict
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def deleteDuplicatesUnsorted(self, head):
“””
:type head: ListNode
:rtype: ListNode
“””
storage = defaultdict(int)
sentinel = ListNode()
sentinel.next = head
cur = head
prev = sentinel
while cur:
storage[cur.val] += 1
cur = cur.next
cur = head
while cur:
if storage[cur.val] > 1:
prev.next = cur.next
else:
prev = cur
cur = cur.next
return sentinel.next
~~~
O(n), O(n)
- LRU Cache
Solved
Medium
Companies: Facebook, many others
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 1:
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]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 3000
0 <= key <= 104
0 <= value <= 105
At most 2 * 105 calls will be made to get and put.
15 minutes assigned
https://leetcode.com/problems/lru-cache/description/
class ListNode:
def \_\_init\_\_(self, key=0, val=0,prev=None, next=None):
self.val = val
self.key = key
self.next = next
self.prev = prev
class LRUCache(object):
def \_\_init\_\_(self, capacity):
"""
:type capacity: int
"""
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.cur_size = 0
self.keys = {}
def bring_to_front(self, node):
self.remove(node)
self.insert_front(node)
def insert_front(self, node):
self.head.next.prev, self.head.next, node.next, node.prev = node, node, self.head.next, self.head
def remove_last(self):
node = self.tail.prev
# cant delete if node is head.
if node == self.head:
return
return self.remove(node)
def remove(self, node):
if node == self.head or node == self.tail:
return None
node.prev.next, node.next.prev = node.next, node.prev
return node
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in self.keys:
node = self.keys[key]
ret = node.val
self.bring_to_front(node)
return ret
else:
return -1
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self.keys:
self.keys[key].val = value
self.bring_to_front(self.keys[key])
return
if self.cur_size == self.capacity:
last = self.remove_last()
del(self.keys[last.key])
self.cur_size -= 1
insert = ListNode(key, value)
self.insert_front(insert)
self.keys[key] = insert
self.cur_size += 1
