added learn-cards problems

AlveeM · AlveeM · commit a7aaa85e8bab · 2021-04-22T11:21:05.000-04:00
diff --git a/leetcode/learn-cards/linked-list/01_design_linked_list_singly_linked.py b/leetcode/learn-cards/linked-list/01_design_linked_list_singly_linked.py
@@ -0,0 +1,93 @@
+class Node:
+    def __init__(self, val):
+        self.val = val
+        self.next = None
+
+class MyLinkedList:
+
+    def __init__(self):
+        """
+        Initialize your data structure here.
+        """
+        self.head = None
+
+    def get(self, index: int) -> int:
+        """
+        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
+        """
+        cur = self.getNodeAtIndex(index)
+        if cur is not None:
+            return cur.val
+        else:
+            return -1
+
+    def addAtHead(self, val: int) -> None:
+        """
+        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
+        """
+        new_head = Node(val)
+        new_head.next = self.head
+        self.head = new_head
+        return
+
+    def addAtTail(self, val: int) -> None:
+        """
+        Append a node of value val to the last element of the linked list.
+        """
+        if self.head is None:
+            self.addAtHead(val)
+            return
+    
+        new_node = Node(val)
+        old_tail = self.getTail()
+        old_tail.next = new_node
+
+    def addAtIndex(self, index: int, val: int) -> None:
+        """
+        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
+        """
+        if index == 0:
+            self.addAtHead(val)
+            return 
+        
+        prev = self.getNodeAtIndex(index - 1)
+        if prev is None:
+            return
+        
+        new_node = Node(val)
+        next_node = prev.next
+        new_node.next = next_node
+        prev.next = new_node
+
+    def deleteAtIndex(self, index: int) -> None:
+        """
+        Delete the index-th node in the linked list, if the index is valid.
+        """
+        cur = self.getNodeAtIndex(index)
+        if cur is None:
+            return
+        
+        prev = self.getNodeAtIndex(index - 1)
+        next_node = cur.next
+        
+        if prev is not None:
+            prev.next = next_node
+        else:
+            self.head = next_node
+    
+    def getNodeAtIndex(self, index: int) -> 'Node':
+        if index < 0: 
+            return None
+        
+        cur = self.head
+        i = 0
+        while i < index and cur is not None:
+            cur = cur.next
+            i += 1
+        return cur
+    
+    def getTail(self) -> 'Node':
+        cur = self.head
+        while cur is not None and cur.next is not None:
+            cur = cur.next
+        return cur
diff --git a/leetcode/learn-cards/linked-list/02_linked_list_cycle.py b/leetcode/learn-cards/linked-list/02_linked_list_cycle.py
@@ -0,0 +1,13 @@
+class Solution:
+    def hasCycle(self, head: ListNode) -> bool:
+        slow = head
+        fast = head
+        
+        while fast and fast.next:
+            slow = slow.next
+            fast = fast.next.next
+            
+            if slow == fast:
+                return True
+            
+        return False
diff --git a/leetcode/learn-cards/linked-list/03_linked_list_cycle_II.py b/leetcode/learn-cards/linked-list/03_linked_list_cycle_II.py
@@ -0,0 +1,21 @@
+class Solution:
+    def detectCycle(self, head: ListNode) -> ListNode:
+        slow = head
+        fast = head
+        
+        while fast and fast.next:
+            slow = slow.next
+            fast = fast.next.next
+            
+            if slow == fast:
+                break
+                
+        if not fast or not fast.next:
+            return None
+        
+        slow = head
+        while slow != fast:
+            slow = slow.next
+            fast = fast.next
+        
+        return slow
diff --git a/leetcode/learn-cards/linked-list/04_intersection_of_two_linked_lists.py b/leetcode/learn-cards/linked-list/04_intersection_of_two_linked_lists.py
@@ -0,0 +1,10 @@
+class Solution:
+    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
+        p1 = headA
+        p2 = headB
+        
+        while p1 != p2:
+            p1 = headB if p1 is None else p1.next
+            p2 = headA if p2 is None else p2.next
+        
+        return p1
diff --git a/leetcode/learn-cards/linked-list/05_remove_nth_node_from_end_of_list.py b/leetcode/learn-cards/linked-list/05_remove_nth_node_from_end_of_list.py
@@ -0,0 +1,17 @@
+class Solution:
+    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
+        slow = head
+        fast = head
+        
+        for _ in range(n):
+            fast = fast.next
+            
+        if not fast:
+            return head.next
+        
+        while fast.next:
+            slow = slow.next
+            fast = fast.next
+            
+        slow.next = slow.next.next
+        return head
diff --git a/leetcode/learn-cards/linked-list/06_reverse_linked_list.py b/leetcode/learn-cards/linked-list/06_reverse_linked_list.py
@@ -0,0 +1,10 @@
+class Solution:
+    def reverseList(self, head: ListNode) -> ListNode:
+        if not head or not head.next:
+            return head
+        
+        reversedHead = self.reverseList(head.next)
+        head.next.next = head
+        head.next = None
+        
+        return reversedHead
diff --git a/leetcode/learn-cards/linked-list/07_remove_linked_list_elements.py b/leetcode/learn-cards/linked-list/07_remove_linked_list_elements.py
@@ -0,0 +1,27 @@
+class Solution:
+    def removeElements(self, head: ListNode, val: int) -> ListNode:
+        dummy = ListNode()
+        dummy.next = head
+        prev = dummy
+        cur = head
+        
+        while cur:
+            if cur.val == val:
+                prev.next = cur.next
+            else:
+                prev = cur
+            
+            cur = cur.next
+            
+        return dummy.next
+
+class Solution2:
+    def removeElements(self, head: ListNode, val: int) -> ListNode:
+        if not head: return None
+        
+        head.next = self.removeElements(head.next, val)
+        
+        if head.val == val:
+            return head.next
+        
+        return head
diff --git a/leetcode/learn-cards/linked-list/08_odd_even_linked_list.py b/leetcode/learn-cards/linked-list/08_odd_even_linked_list.py
@@ -0,0 +1,23 @@
+class Solution:
+    def oddEvenList(self, head: ListNode) -> ListNode:
+        if not head or not head.next: return head
+        
+        odd_head = head
+        even_head = head.next
+        odd = odd_head
+        even = even_head
+        
+        while even:
+            if even.next:
+                odd.next = even.next
+            else:
+                odd.next = even_head
+                return odd_head
+            
+            odd.next = even.next
+            odd = odd.next
+            even.next = odd.next
+            even = even.next
+        
+        odd.next = even_head
+        return odd_head
diff --git a/leetcode/learn-cards/linked-list/09_palindrome_linked_list.py b/leetcode/learn-cards/linked-list/09_palindrome_linked_list.py
@@ -0,0 +1,52 @@
+class Solution:
+    def isPalindrome(self, head: ListNode) -> bool:
+        self.left = head
+        
+        def isPalindromeRec(node):
+            if node is not None: 
+                if not isPalindromeRec(node.next):
+                    return False
+                if self.left.val != node.val:
+                    return False
+                self.left = self.left.next
+            
+            return True
+        
+        return isPalindromeRec(head)
+
+class Solution2:
+    def isPalindrome(self, head: ListNode) -> bool:
+        if not head: return True
+        
+        mid = self.findMid(head)
+        second_half_start = self.reverseList(mid.next)
+        
+        res = True
+        left = head
+        right = second_half_start
+        while res and right:
+            if left.val != right.val:
+                res = False
+            left = left.next
+            right = right.next
+            
+        mid.next = self.reverseList(second_half_start)
+        return res
+    
+    def findMid(self, head):
+        slow = head
+        fast = head
+        while fast.next and fast.next.next:
+            slow = slow.next
+            fast = fast.next.next
+        return slow
+    
+    def reverseList(self, head):
+        prev = None
+        cur = head
+        while cur:
+            next_node = cur.next
+            cur.next = prev
+            prev = cur
+            cur = next_node
+        return prev
diff --git a/leetcode/learn-cards/linked-list/10_design_doubly_linked_list.py b/leetcode/learn-cards/linked-list/10_design_doubly_linked_list.py
diff --git a/leetcode/learn-cards/linked-list/11_merge_two_sorted_lists.py b/leetcode/learn-cards/linked-list/11_merge_two_sorted_lists.py
@@ -0,0 +1,11 @@
+class Solution:
+    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
+        if not l1 or not l2:
+            return l1 or l2
+        
+        if l1.val < l2.val:
+            l1.next = self.mergeTwoLists(l1.next, l2)
+            return l1
+        else:
+            l2.next = self.mergeTwoLists(l1, l2.next)
+            return l2
diff --git a/leetcode/learn-cards/linked-list/12_add_two_numbers.py b/leetcode/learn-cards/linked-list/12_add_two_numbers.py
@@ -0,0 +1,20 @@
+class Solution:
+    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
+        head = ListNode(0)
+        cur = head
+        carry = 0
+        
+        while any([l1, l2, carry]):
+            v1 = l1.val if l1 else 0
+            v2 = l2.val if l2 else 0
+            total = v1 + v2 + carry
+            
+            carry, res = divmod(total, 10)
+            
+            cur.next = ListNode(res)
+            cur = cur.next
+            
+            l1 = l1.next if l1 else None
+            l2 = l2.next if l2 else None
+        
+        return head.next
diff --git a/leetcode/learn-cards/linked-list/13_flatten_a_multilevel_doubly_linked_list.py b/leetcode/learn-cards/linked-list/13_flatten_a_multilevel_doubly_linked_list.py
@@ -0,0 +1,49 @@
+class Solution:
+    def flatten(self, head: 'Node') -> 'Node':
+        if not head: return None
+        self.flattenRec(head)
+        return head
+    
+    def flattenRec(self, node):
+        cur = node
+        tail = node
+        
+        while cur:
+            child = cur.child
+            next_node = cur.next
+            if child:
+                new_tail = self.flattenRec(child)
+                new_tail.next = next_node
+                if next_node:
+                    next_node.prev = new_tail
+                cur.next = child
+                child.prev = cur
+                cur.child = None
+                cur = tail
+            else:
+                cur = next_node
+            
+            if cur:
+                tail = cur
+        
+        return tail
+
+class Solution2:
+    def flatten(self, head: 'Node') -> 'Node':
+        
+        def dfs(prev, curr):
+            if not curr:
+                return prev
+            prev.next = curr
+            curr.prev = prev
+            rest = curr.next
+            tail = dfs(curr, curr.child)
+            curr.child = None
+            return dfs(tail, rest)
+        
+        if not head:
+            return head
+        sentinel = Node()
+        dfs(sentinel, head)
+        sentinel.next.prev = None
+        return sentinel.next
