<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 sortList ( 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> prev , fast , slow = slow , fast . next . next , slow . next <EOL> prev . next = None <EOL> sorted_l1 = self . sortList ( head ) <EOL> sorted_l2 = self . sortList ( slow ) <EOL> return self . mergeTwoLists ( sorted_l1 , sorted_l2 ) <EOL> def mergeTwoLists ( self , l1 , l2 ) : <EOL> dummy = ListNode ( <NUM_LIT:0> ) <EOL> cur = dummy <EOL> while l1 != None and l2 != None : <EOL> if l1 . val <= l2 . val : <EOL> cur . next , cur , l1 = l1 , l1 , l1 . next <EOL> else : <EOL> cur . next , cur , l2 = l2 , l2 , l2 . next <EOL> if l1 != None : <EOL> cur . next = l1 <EOL> if l2 != None : <EOL> cur . next = l2 <EOL> return dummy . next <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> head = ListNode ( <NUM_LIT:3> ) <EOL> head . next = ListNode ( <NUM_LIT:4> ) <EOL> head . next . next = ListNode ( <NUM_LIT:1> ) <EOL> head . next . next . next = ListNode ( <NUM_LIT:2> ) <EOL> print Solution ( ) . sortList ( head ) </s>
