Leetcode 143. Reorder List

https://leetcode.com/problems/reorder-list/

Still simple. 3 steps to do the task: cut, reverse and merge. Concerning the cut process, we can use the slow and fast pointers-- they are really useful.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param head, a ListNode
    # @return nothing
    def reorderList(self, head):
        if head == None or head.next == None:
            return
        
        fast, slow, prev = head, head, None
        while fast != None and fast.next != None:
            fast, slow, prev = fast.next.next, slow.next, slow
        current, prev.next, prev = slow, None, None
        
        while current != None:
            current.next, prev, current = prev, current, current.next
            
        l1, l2 = head, prev
        dummy = ListNode(0)
        current = dummy

        while l1 != None and l2 != None:
            current.next, current, l1 = l1, l1, l1.next
            current.next, current, l2 = l2, l2, l2.next
            
        return

Run Time: 168 ms