Day 13 of LeetCode

Q1

19. Remove Nth Node From End of List

Medium. Linked list, two pointers

Use a dummy node to find the node before the target node.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        # left pointer will point to the node before the target node
        left = dummy
        right = head

        # Shift right pointer
        while n > 0 and right:
            right = right.next
            n -= 1
        # Shift left and right pointers
        while right:
            left = left.next
            right = right.next

        # Delete
        left.next = left.next.next

        return dummy.next

Q2

138. Copy List with Random Pointer

Medium. Linked list, two passes

Two passes:

1. First pass to set up the values and hashmap

2. Second pass sets up the links (next and random)

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # hashmap to map the old and copy node
        oldToCopy = { None:None } # Remember to initialize the None mapping

        # First pass to set the values and hashmap
        curr = head
        while curr:
            copy = Node(curr.val)
            oldToCopy[curr] = copy
            curr = curr.next

        # Second pass to set up the links
        curr = head
        while curr:
            copy = oldToCopy[curr]
            copy.next = oldToCopy[curr.next]
            copy.random = oldToCopy[curr.random]
            curr = curr.next

        return oldToCopy[head]

Q3

2. Add Two Numbers

Medium. Linked list

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy

        carry = 0
        # Loop til the longer list and carry == 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            val = v1 + v2 + carry
            # e.g. val == 15
            carry = val // 10 # 1
            val = val % 10 # 5

            curr.next = ListNode(val)

            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next