[leetcode] linkedlist

def (self, head: ListNode, k: int) -> ListNode:
    if not head:
        return None
    cur = head
    cnt = 0
    stack = []
    while cur and len(stack) < k:
        stack.append(cur)
        cur = cur.next
    if len(stack) < k:
        return head
    newhead = stack.pop()
    res = newhead
    while stack:
        newhead.next = stack.pop()
        newhead = newhead.next
    
    newhead.next = self.reverseKGroup(cur, k)
    return res

def reverseBetween(self, head, m, n):
    """
    :type head: ListNode
    :type m: int
    :type n: int
    :rtype: ListNode
    """
    cur = head
    prev = None
    for i in range(m - 1):
        prev = cur
        cur = cur.next
    tail = cur
    r = None
    for i in range(n - m + 1):
        n = cur.next
        cur.next = r
        r = cur
        cur = n
    tail.next = n
    if prev:
        prev.next = r
    if m == 1:
        return r
    return head

def swapPairs(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    cur = head
    res = ListNode(0)
    dummy = res
    while cur:
        _next = cur.next
        if not _next:
            dummy.next = cur
            break
        unsorted = _next.next
        _next.next, cur.next = cur, None
        dummy.next = _next
        dummy = cur
        cur = unsorted
    return res.next

class Solution(object):
    def __init__(self):
        self.visited = {}
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return
        if head in self.visited:
            return self.visited[head]
        
        node = Node(head.val, None, None)
        self.visited[head] = node
        node.next = self.copyRandomList(head.next)
        node.random = self.copyRandomList(head.random)
        return node

def partition(self, head: ListNode, x: int) -> ListNode:
    small_head, large_head = ListNode(0), ListNode(0)
    small, large = small_head, large_head
    cur = head
    while cur:
        if cur.val < x:
            small.next = cur
            small = small.next
        if cur.val >= x:
            large.next = cur
            large = large.next
        cur = cur.next
    large.next = None 
    small.next = large_head.next
    return small_head.next

def nextLargerNodes(self, head):
    stack = [] # [[0,2]]
    index = 0
    d = collections.defaultdict(int)
    while head:
        while stack and stack[-1][1] < head.val:
            v = stack.pop()
            d[v[0]] = head.val
        stack.append([index, head.val])
        index += 1
        head = head.next
    res = [0] * index
    for i in range(len(res)):
        res[i] = d[i]
    return res