from ..notes import gcd
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def insertGreatestCommonDivisors(self, head: ListNode) -> ListNode:
node = head
while node.next:
node.next = ListNode(val=gcd(node.val, node.next.val), next=node.next)
node = node.next.next
return head
from typing import Optional
class Node:
def __init__(
self,
value=0,
key=0, # for eviction
left: Optional['Node'] = None,
right: Optional['Node'] = None,
):
self.key = key
self.value = value
self.left = left
self.right = right
def append(self, node: 'Node'):
node.left = self
node.right = self.right
if self.right:
self.right.left = node
self.right = node
def isolate(self):
if self.left:
self.left.right = self.right
if self.right:
self.right.left = self.left
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dict: dict[int, Node] = {}
self.fresh = Node()
self.stale = Node()
self.fresh.right = self.stale
self.stale.left = self.fresh
self.amount = 0
def get(self, key: int) -> int:
node = self.dict.get(key, Node(-1))
if key in self.dict:
node.isolate()
self.fresh.append(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.dict:
self.dict[key].isolate()
else:
if self.amount == self.capacity:
evicted = self.stale.left
if evicted:
evicted.isolate()
self.dict.pop(evicted.key)
else:
self.amount += 1
node = self.dict.setdefault(key, Node(key=key))
self.fresh.append(node)
node.value = value
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution1:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
l = r = d = ListNode(next=head)
for _ in range(n - 1):
r = r.next
while r.next and r.next.next is not None:
l, r = l.next, r.next
l.next = l.next.next
return d.next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
l = r = head
for _ in range(n):
r = r.next
if r is None:
return head.next
while r.next:
l, r = l.next, r.next
l.next = l.next.next
return head
class Solution:
def detectCycle(self, head):
'''
.___a___.___C-b___.
(_________) -> C: cycle
b
slow: a+C-b + xC
fast: a+C-b + yC
2 slow = fast
=> a+C-b = (y-2x)C
=> a = (y-2x-1)C+b
.___(y-2x-1)C+b___.___C-b___.
(_________)
b
=> a mod C = b mod C
'''
l = r = head
while r and r.next:
l, r = l.next, r.next.next
if l is r:
break
else:
return
while head is not r:
head, r = head.next, r.next
return head