class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def get_ll():
    s = '18701479008'
    head = ListNode()
    pre = head
    for c in s:
        cur = ListNode(int(c))
        pre.next = cur
        pre = cur
    return head.next

def get_circle_ll():
    head = get_ll()
    cur = head
    node_4 = None
    while cur.next:
        if cur.val == 4:
            node_4 = cur

        cur = cur.next
    cur.next = node_4

    return head



def traverse_ll(head):
    curr = head
    while curr:
        print(curr.val, end=" -> ")
        curr = curr.next
    print('Nil')

def reverse_ll(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

def find_middle_ll(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def check_circle_ll(head):
    slow = fast = head

    while fast and fast.next:
        if slow == fast:
            return True
        slow = slow.next
        fast = fast.next.next
    return False

def find_circle_start_ll(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None

    slow = head
    while slow:
        slow = slow.next
        fast = fast.next
        if slow == fast:
            break
    return slow

class DoubleListNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

def double_reverse(head):
    cur = head
    pre = None

    while cur:
        nxt = cur.next
        cur.next = pre
        cur.prev = nxt
        pre = cur
        cur = nxt
    return pre

# LRU

class Node:
    def __init__(self, k, v):
        self.k = k
        self.v = v
        self.prev = None
        self.next = None


class LRU:
    def __init__(self, cap=10):
        self.cap = cap
        head = Node(-1, -1)
        tail = Node(-1, -1)
        head.next = tail
        tail.prev = head
        self.h = {}
        self.head = head
        self.tail = tail

    def get(self, k):
        node = self.h.get(k, None)
        if node:
            self._put_to_tail(node)
        else:
            return -1
        return node.v

    def put(self, k, v):
        if k in self.h:
            node = self.h[k]
            node.v = v
            return self._put_to_tail(node)
        if self.cap == len(self.h):
            self._remove_head()
        node = Node(k, v)
        self.h[k] = node
        return self._put_to_tail(node)

    def _put_to_tail(self, node):
        tail = self.tail
        prev = tail.prev
        prev.next = node
        node.next = tail
        node.prev = prev
        tail.prev = node
        return

    def _remove_head(self):
        head = self.head
        first = head.next
        second = first.next
        head.next = second
        second.prev = head
        return