プログラミングトレーニング(06/09/2021)

プログラミングトレーニング(06/09/2021)

競技プログラミングの練習メモです。

[LeetCode][Easy] 160. Intersection of Two Linked Lists


https://leetcode.com/problems/intersection-of-two-linked-lists/

ハッシュを利用して time/space O(N + M) で解く方法で簡単に解けた。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        hash_table = set()
        while headA:
            hash_table.add(headA)
            headA = headA.next
        
        while headB:
            if headB in hash_table:
                return headB
            headB = headB.next
        
        return None

Space O(1) で解く方法は全然思い付かなくて、回答をチラ見してあーなるほどなと理解した。これその場で思い付けるものだろうか。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        nodeA = headA
        nodeB = headB
        while nodeA != nodeB:
            nodeA = headB if nodeA is None else nodeA.next
            nodeB = headA if nodeB is None else nodeB.next

        return nodeA

[LeetCode][Medium] 19. Remove Nth Node From End of List


2パスでやる方法は思い付いて解けた。ちょっと綺麗ではないけど。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        node = head
        list_len = 0
        while node:
            node = node.next
            list_len += 1
        
        prev = None
        node = head
        for _ in range(list_len - n):
            prev = node
            node = node.next
        
        if prev == None:
            return node.next

        prev.next = node.next
        
        return head

[LeetCode][Easy] 206. Reverse Linked List


https://leetcode.com/problems/reverse-linked-list/

久しぶりに解いたあれって解けなかった。。。要復習だなこれ。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        node = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return node

[LeetCode][Easy] 203. Remove Linked List Elements


https://leetcode.com/problems/remove-linked-list-elements/

再帰コールで解けたけど、Space O(1) の while ループで解く方法が出来なくてこれもまた要復習。。

class Solution:
    def removeElements(self, node: ListNode, val: int) -> ListNode:
        if node is None:
            return None
        
        if node.val == val:
            return self.removeElements(node.next, val)
        
        node.next = self.removeElements(node.next, val)
        return node

[LeetCode][Medium] 328. Odd Even Linked List


https://leetcode.com/problems/odd-even-linked-list/

解法の考え方は正しかったけど、解けなかった。。

class Solution:
    def oddEvenList(self, node: ListNode) -> ListNode:
        if node is None or node.next is None:
            return node
        
        head = node

        odd = head
        even = head.next 
        even_head = even
        
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            
            even.next = odd.next
            even = even.next
        
        odd.next = even_head
        
        return head


See also