[LeetCode]

Solution)class Solution: def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]: # under is a list with nodes whose values are under x # over is a list with nodes whose values are over x under, over = ListNode(0), ListNode(0) dUnder, dOver = under, over while head: # If the cur node's value is greater than x connect to over if head.val >= x: over.next = head over = over.next..

Solution) class Solution: def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # Base Case if not head: return None # Two Pointers slow, fast = head, head # Find length and send fast to the end of the list length = 1 while fast.next: fast = fast.next length += 1 fast.next = head # Reduce k and move slow k %= length for i in range(length-k-1): slow = slow.next # Connect ..

Solution)class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: # Base Case if not head: return None # Dummy Node dummy = ListNode(0, head) # dup's initial value is a value that # a node cannot have in this problem prev, cur = dummy, head dup = -101 while cur.next: # If a duplicate is found, save that value if cur.val == cur.next.val: dup = cur.val # If the c..

Solution) class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: # Dummy node that allows us to access head dummy = ListNode(0, head) # Dictionary that saves {index:node} indexDic = {0:dummy} # Save {index:node} to indexDic nodeIndex = 1 while head: indexDic[nodeIndex] = head head = head.next nodeIndex += 1 # Find the index whose node has to be remove..

Solution)class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: # cur iterates the linked list # checkpoint is the node right before the reversal cur, checkpoint = head, head # Move cur to a node where the reversal starts for _ in range(left - 1): checkpoint = cur cur = cur.next # reverse is the head of reversed linked list # tail is the ..

Solution) class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': # Base Case if not head: return None # Checkpoints that will save the heads of each linked list original = head root = Node(head.val) # Dictionary that will save {original node : copied node} # Those paired nodes have the same value. dic = {head:root} # Deepcopy each node and link them # without conne..

Solution) class Solution: def evalRPN(self, tokens: List[str]) -> int: # Initialization stack = [] for tk in tokens: if tk == "+": stack.append(stack.pop() + stack.pop()) elif tk == "*": stack.append(stack.pop() * stack.pop()) # Careful with the order of operand elif tk == "-": stack.append(-stack.pop() + stack.pop()) # Careful with the order of operand and floor division elif tk == "/": right, ..

Solution) class MinStack: def __init__(self): self.stack = [] self.minVal = float('inf') def push(self, val: int) -> None: # Append a tuple in a form of (val, previous minVal) self.stack.append((val, self.minVal)) # Update minVal if need to self.minVal = min(self.minVal, val) def pop(self) -> None: # When we pop, we might pop a tuple that has a value of minVal # so we update minVal to a previous..

Solution) class Solution: def simplifyPath(self, path: str) -> str: # Split so that we only have the directories path = path.split('/') # res will save canonical path res = [] for directory in path: # Need to go to the directory up a level so we pop if directory == "..": if res: res.pop() # We're still in the current directory so we don't do anything elif directory == '.': continue # Append dire..

Solution) class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: # Initialization points.sort() res = [points[0]] for start, end in points[1:]: # If the cur interval and prev interval overlap # find the part that only overlaps with no leftover if start int: points.sort() res = [points[0]] for start, end in points[1:]: if start