@@ -0,0 +1,1702 @@
+# Problem description:      Given a linked list, sort it using insertion sort.%0A# Solution time complexity: O(n%5E2)%0A# Comments:                 Dummy node technique. The isSorted() test is optimization and is not part%0A#                           of the insertion sort algorithm.%0A%0A%22%22%22%0ADefinition of ListNode%0Aclass ListNode(object):%0A%0A    def __init__(self, val, next=None):%0A        self.val = val%0A        self.next = next%0A%22%22%22%0Aclass Solution:%0A    %22%22%22%0A    @param head: The first node of linked list.%0A    @return: bool, True if empty or for each pair of %0A             nodes in the list, n1 and n2:%0A                n1.val %3C= n2.val%0A            else False.%0A    %22%22%22%0A    @staticmethod%0A    def isSorted(head):%0A        if head == None:%0A            return True%0A            %0A        cur = head%0A        nxt = head.next%0A        %0A        while nxt != None:%0A            if cur.val %3E nxt.val:%0A                return False%0A            else:%0A                cur = cur.next%0A                nxt = nxt.next%0A                %0A        return True%0A    %0A    %22%22%22%0A    @param head: The first node of linked list.%0A    @return: The head of linked list.%0A    %22%22%22 %0A    def insertionSortList(self, head):%0A        if head == None:%0A            return None%0A        %0A        if Solution.isSorted(head):%0A            return head%0A        %0A        dummy = ListNode(0)%0A        node  = head%0A        %0A        while node != None:%0A            temp = node.next%0A            dest = dummy%0A            %0A            while dest.next != None and node.val %3E dest.next.val:%0A                dest = dest.next%0A            %0A            node.next = dest.next%0A            dest.next = node%0A            %0A            node      = temp%0A            %0A        return dummy.next%0A

Create solution.py