147.md

Insertion Sort List

Description

link

---

Solution

See Code

• cur节点代表了寻找位置的指针节点，当cur>head的时候，重置为第一个
• 无论是否重置，都从cur开始寻找head的位置
• 插入head

---

Code

O(n)

# 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
        """
        cur = dummy = ListNode(0)
        while head:
            if cur.val > head.val: # reset pointer only when new number is smaller than pointer value
                cur = dummy
            while cur.next and cur.next.val < head.val: # classic insertion sort to find position
                cur = cur.next
            cur.next, cur.next.next, head = head, cur.next, head.next # insert
        return dummy.next