Question: https://oj.leetcode.com/problems/insertion-sort-list/
Question Name: Insertion Sort List
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param head, a ListNode # @return a ListNode def insertionSortList(self, head): if head == None: return None # Cut the list into two part: sorted and to-sort. pseudoHead = ListNode(-1) # Sorted list pseudoHead.next = head current = head.next # To-sort list head.next = None # Cut the two lists sortedEnd = head # Optimization for sorted input while current != None: # Store the current's next for later use. nextCurrent = current.next if sortedEnd.val <= current.val: # Append the current node at the end. sortedEnd.next = current current.next = None # The node at the end of sorted list is changed. sortedEnd = current else: # Insert to some place in the middle of sorted list headOfSorted = pseudoHead # Find the insert position. If space permitted, we could use # a binary tree to record the sorted node. So that we could # find the insert position with O(logN) instead of O(N). # # Because this current node will not be added at the end, we # do not need to check the bound. while headOfSorted.next.val < current.val: headOfSorted = headOfSorted.next # Insert the node current.next = headOfSorted.next headOfSorted.next = current current = nextCurrent return pseudoHead.next |