Skip to content

Instantly share code, notes, and snippets.

View 142. Linked List Cycle II.py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
"""
Thought Process:
We use hashmap to store node we visted already, if current node in the hashmap, it mean there's cycle and it's first node starting a cycle.
View 160. Intersection of Two Linked Lists.py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
"""
PC:
- no cycle return None
View 141. Linked List Cycle.py
class Solution:
def hasCycle(self, head: ListNode) -> bool:
"""
T:O(n) If there's no cycle, apparently, it's O(n). If there's cycle, O(N+K), N is non-cyclic length and K is alsmot cyclic lengh, in total is O(n).
---xxxxx
K comes from how many iterations we needed for xxxx==it's logest distance between 2 runners / difference of speed. So, it's almost K/1
"""
return self.detect_cycle(head)
View 876. Middle of the Linked List.py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
"""
PC:
what if length of Linked List is even, there's two middle one. Is okay to just return the second one
View 82. Remove Duplicates from Sorted List II.py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
"""
不囉唆, remove nodes we need to initialize two pointers prev and cur
d -> 1 ->1->1->1
prev cur
View 203. Remove Linked List Elements.py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
"""
d->7->-7>-7->7
perv cur
"""
View 83. Remove Duplicates from Sorted List.py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
"""
we need two pointers called prev and cur
-Initially, cur is one step forward to prev pointer.
View 1049. Last Stone Weight II.py
class Solution:
"""
we enumerate all possible combinations when cosidring all stones.
O(2^n)
"""
def lastStoneWeightII(self, stones: List[int]) -> int:
"""
T: O(n*2M), where n =len(stones) and M = sum(stones). At most, we need to caclulate n*M possibilties.
because same path will be casched.
n comes from depth of recursion tree and M comes from at most our left_sum could be.
View 494. Target Sum.py
class Solution:
"""
To clarify:
what's range of S?
what's range of nums? sum(nums) <= 1000 and len(nums) <= 20
"""
def findTargetSumWays(self, nums: List[int], S: int) -> int:
"""
Brute Force
T:O(2^n)
View 545. Boundary of Binary Tree.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
"""
Problem Clarification:
Can I assume value of node in the tree is unique? No