Learning On the Way

143. Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

def reorderList(self, head: ListNode) -> None: 
    if not head: 
        return  
        
    # find the middle of linked list [Problem 876] 
    # in 1->2->3->4->5->6 find 4  
    slow = fast = head 
    while fast and fast.next: 
        slow = slow.next 
        fast = fast.next.next  
            
    # reverse the second part of the list [Problem 206] 
    # convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4 
    # reverse the second half in-place 
    prev, curr = None, slow 
    while curr: 
        curr.next, prev, curr = prev, curr, curr.next        
    # merge two sorted linked lists [Problem 21] 
    # merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4 
    first, second = head, prev 
    while second.next: 
        first.next, first = second, first.next 
        second.next, second = first, second.next