147.md

147. Insertion Sort List

Sort a linked list using insertion sort.

my thoughts:

1. use a dummy head and insert each node after the dummy.

my solution:

**********1488ms
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        def ins(n, d):
            p0, p1 = d, d.next
            while p1 and n.val >= p1.val:
                p0 = p1
                p1 = p1.next
            p0.next = n
            n.next = p1
        
        dummy = ListNode(0)
        dummy.next = head
        p1 = head.next
        head.next = None
        while p1:
            p2 = p1.next            
            ins(p1, dummy)
            p1 = p2
            
        return dummy.next

my comments:

from other ppl's solution:

1. in place, 399ms:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        
        dummy = ListNode(0) #Add head node to the list
        
        dummy.next = head
        
        curr = head
        
        while curr.next:
            if curr.next.val < curr.val: # The curr pointer moves backwards if the list is in ascending order 
                prev = dummy     # until the value of one node is less than the value of the previous 
                
                while prev.next.val < curr.next.val: # Look for inserted position
                    prev = prev.next
                    
                
                temp = curr.next # Diagram
                curr.next = temp.next
                temp.next = prev.next
                prev.next = temp
            
            else:
                curr = curr.next
                
        return dummy.next