143. Reorder List

key points: 
-simultaneous assignment 
-dummy head node to thread linked lists 
-use prev node to reverse linked list 

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        #divide the list into two halves, prev is the node before the starting node of second list 
        if head is None or head.next is None: return  
        slow,fast,prev=head,head,None 
        while fast and fast.next  :
            prev,slow,fast=slow,slow.next,fast.next.next
        
        
        #reverse the second list 
        current,prev.next,prev=slow,None,None
        while current:
            current.next,prev,current=prev,current,current.next
            
        #create a dummy head and thread two list one by one 
        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