[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の前に仮想ノードを追加し、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良い解決策のようです.

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

root.leftの右側の子の中で、末尾の子を検索します=>r = r.right

見つかった子供の右側にroot.right=>r.right = root.rightを貼ります

root.leftをroot.rightroot.leftに貼り付けてNoneに貼り付けます.

繰り返すと平らになる~
でも問題は私たちが順番にやったことですね.

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

self.prevを使用して右に曲がります
これもいい解決策のようです.