Reorder List

ReorderList.py

    # Leetcode 61: Reorder List
    
    # function to find mid of a list 
    def findMidofList(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    # reverse a list
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev


    # merge two list one node from each at a time
    def mergeList(self, first_list: ListNode, second_list: ListNode):
        # Get head of each list
        head_1 = first_list
        head_2 = second_list

        # only loop till both lists are valid
        while head_1 and head_2:

            # Get two nodes to be connected
            first = head_1
            second = head_2

            # move both list forward
            head_1 = head_1.next
            head_2 = head_2.next

            # isolate the two nodes from their list and connect them
            first.next = None
            second.next = None
            first.next = second

            # reconnect to first list
            second.next = head_1

        return
    
    # print a list 
    def printList(self, head: ListNode) -> ListNode:
        curr = head
        while curr:
            print(curr.val, end=" -> ")
            curr = curr.next
        print("...None...")
        return

    # reorder a list from "L0 → L1 → … → Ln - 1 → Ln" to "L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …"
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        mid = self.findMidofList(head)
        first_list = head
        second_list = mid.next
        mid.next = None
        second_list = self.reverseList(second_list)
        # self.printList(first_list)
        # self.printList(second_list)
        self.mergeList(first_list, second_list)
        # self.printList(head)
        return