[Mock] Random 25

---

203. Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

My Answer 1: Accepted (Runtime: 68 ms - 72.99% / Memory Usage: 17.3 MB - 8.81%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        prev = ListNode(-1, head)
        h = prev
        
        while head:
            while head and head.val == val:
                head = head.next
            prev.next = head
            if head:
                head = head.next
            prev = prev.next
        
        return h.next

head 앞에 dummy node 를 추가해서 prev 잡아주기

반복문 돌면서 head.val 가 val 랑 같으면 다른 값이 나올 때까지 head = head.next

prev 의 next 에 val 가 아닌 값을 넣어주기

head, prev 모두 next 값 가리키도록

if head: 가 있는 이유는 앞에 while 문에서 None 이 될 수도 있기 때문

Solution 1: Accepted (Runtime: 72 ms - 50.37% / Memory Usage: 25.8 MB - 6.39%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if head is None:
            return None
        head.next = self.removeElements(head.next, val);
        return head.next if head.val == val else head

자체를 재귀로 써서 우선 끝까지 간 다음

val 가 아니면 head 를, 같으면 head.next 를 return

좋은 솔루션인듯

---

114. Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a "linked list":

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The "linked list" should be in the same order as a pre-order traversal of the binary tree.

My Answer 1: Accepted (Runtime: 28 ms - 98.34% / Memory Usage: 15.1 MB - 75.25%)

# 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:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        while root:
            r = root.left
            if r:
                while r.right:
                    r = r.right
                r.right = root.right
                root.right = root.left
                root.left = None
            root = root.right

1. root.left 의 오른쪽 자식 중 가장 끝에 있는 자식 찾기 => r = r.right

2. 찾은 자식의 오른쪽에 root.right 붙여주기 => r.right = root.right

3. root.left 를 root.right 로 붙이고 root.left 는 None 으로

반복해주면 flatten 된다~

근데 문제에서 pre-order 로 하라고 한거였구나...

Solution 1: Accepted (Runtime: 32 ms - 92.69% / Memory Usage: 15 MB - 92.12%)

# 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:
    def __init__(self):
        self.prev = None
    
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return None
        
        self.flatten(root.right)
        self.flatten(root.left)

        root.right = self.prev
        root.left = None
        self.prev = root

pre-order 로 순회하면서 self.prev 를 이용해서 right 로 다 몰아주기

이거도 좋은 루션이인듯