【leetcode】147. Insertion Sort List

题目如下：

解题思路：题目不难，每个节点找到对应的位置插入即可。

代码如下：

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

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        newHead = None
        while head != None:
            if newHead == None:
                newHead = ListNode(head.val)
                head = head.next
                continue
            node = newHead
            new_node = ListNode(head.val)

            #insert as the head
            if node.val > head.val:
                new_node.next = newHead
                newHead = new_node
                head = head.next
                continue
            while node != None:
                if node.next != None and node.val <= head.val and node.next.val >= head.val:
                    new_node.next = node.next
                    node.next = new_node
                    break
                elif node.next == None:
                    node.next = new_node
                    break
                node = node.next
            head = head.next
        return newHead