<s> class ListNode : <EOL> def __init__ ( self , x ) : <EOL> self . val = x <EOL> self . next = None <EOL> def __repr__ ( self ) : <EOL> if self : <EOL> return "<STR_LIT>" . format ( self . val , repr ( self . next ) ) <EOL> class Solution : <EOL> def reorderList ( self , head ) : <EOL> if head == None or head . next == None : <EOL> return head <EOL> fast , slow , prev = head , head , None <EOL> while fast != None and fast . next != None : <EOL> fast , slow , prev = fast . next . next , slow . next , slow <EOL> current , prev . next , prev = slow , None , None <EOL> while current != None : <EOL> current . next , prev , current = prev , current , current . next <EOL> l1 , l2 = head , prev <EOL> dummy = ListNode ( <NUM_LIT:0> ) <EOL> current = dummy <EOL> while l1 != None and l2 != None : <EOL> current . next , current , l1 = l1 , l1 , l1 . next <EOL> current . next , current , l2 = l2 , l2 , l2 . next <EOL> return dummy . next <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> head = ListNode ( <NUM_LIT:1> ) <EOL> head . next = ListNode ( <NUM_LIT:2> ) <EOL> head . next . next = ListNode ( <NUM_LIT:3> ) <EOL> head . next . next . next = ListNode ( <NUM_LIT:4> ) <EOL> head . next . next . next . next = ListNode ( <NUM_LIT:5> ) <EOL> print Solution ( ) . reorderList ( head ) </s>
