liyunrui

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    """
    PC:
       -we're not allowed to access head of linked list 

liyunrui

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    d->1->2->2->1
    
    Optimal solution with O(1) space

liyunrui

# 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.

liyunrui

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    """
    PC:
        - no cycle return None

liyunrui

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)
    

liyunrui

# 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
        

liyunrui

# 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

liyunrui

# 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
    """

liyunrui

# 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.

liyunrui

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.