Day 12 of LeetCode

Documenting LeetCode solving.

Q1

206. Reverse Linked List

Easy. Linked list, two pointers.

From Neetcode, youtube.com/watch?v=G0_I-ZF0S38

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        # Two pointers current and previous
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        return prev

Q2

21. Merge Two Sorted Lists

Easy. Linked list

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Good technique: use dummy node
        dummy = ListNode()
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        # Take the longer one
        if list1:
            tail.next = list1
        else:
            tail.next = list2

        return dummy.next

Q3

143. Reorder List

Medium. Linked list

We break the list into left and right parts, reverse right part then merge them.

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # First, find the middle to break the list into two
        slow, fast = head, head.next
        while fast and fast.next:
            # slow will be the end of the left portion
            slow = slow.next
            fast = fast.next.next

        # The head of the right portion
        curr = slow.next
        prev = None
        # Seperate left and right portions
        slow.next = None

        # Reverse the right portion
        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp

        # Merge
        # prev points to the reversed list's head
        first, second = head, prev
        while second: # Right portion is shorter
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2