<s> __author__ = '<STR_LIT>' <EOL> class ListNode : <EOL> def __init__ ( self , x ) : <EOL> self . val = x <EOL> self . next = None <EOL> class Solution : <EOL> def insertionSortList_TLE ( self , head ) : <EOL> """<STR_LIT>""" <EOL> comparator = lambda x , y : cmp ( x . val , y . val ) <EOL> dummy_head = ListNode ( <NUM_LIT:0> ) <EOL> dummy_head . next = head <EOL> closed_tail = dummy_head . next <EOL> while ( closed_tail and closed_tail . next ) : <EOL> open_head = closed_tail . next <EOL> ptr_before = dummy_head <EOL> ptr = dummy_head . next <EOL> while ( ptr_before ) : <EOL> if comparator ( ptr , open_head ) > <NUM_LIT:0> : <EOL> ptr_before . next = open_head <EOL> closed_tail . next = open_head . next <EOL> open_head . next = ptr <EOL> break <EOL> if ptr == open_head : <EOL> closed_tail = closed_tail . next <EOL> break <EOL> ptr_before = ptr_before . next <EOL> ptr = ptr . next <EOL> return dummy_head . next <EOL> def insertionSortList ( self , head ) : <EOL> """<STR_LIT>""" <EOL> comparator = lambda x , y : cmp ( x . val , y . val ) <EOL> dummy = ListNode ( <NUM_LIT:0> ) <EOL> dummy . next = head <EOL> closed_tail = head <EOL> while ( closed_tail and closed_tail . next ) : <EOL> open_head = closed_tail . next <EOL> open_head_next = closed_tail . next . next <EOL> if not comparator ( closed_tail , open_head ) <= <NUM_LIT:0> : <EOL> pre = dummy <EOL> while comparator ( pre . next , open_head ) < <NUM_LIT:0> : <EOL> pre = pre . next <EOL> open_head . next = pre . next <EOL> pre . next = open_head <EOL> closed_tail . next = open_head_next <EOL> else : <EOL> closed_tail = closed_tail . next <EOL> return dummy . next <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import random <EOL> lst = [ ListNode ( i ) for i in random . sample ( xrange ( - <NUM_LIT:1000> , <NUM_LIT:1000> ) , <NUM_LIT:1000> ) ] <EOL> for i in range ( len ( lst ) ) : <EOL> try : <EOL> lst [ i ] . next = lst [ i + <NUM_LIT:1> ] <EOL> except IndexError : <EOL> lst [ i ] . next = None <EOL> head = Solution ( ) . insertionSortList ( lst [ <NUM_LIT:0> ] ) <EOL> current = head <EOL> for i in range ( len ( lst ) ) : <EOL> print current . val <EOL> current = current . next </s>
