147. Insertion Sort List

题目

Sort a linked list using insertion sort.

思路

这道题花费了最多的时间。

1. 复习了array的插入排序，用两个循环实现，每次循环到下一个数，和之前的比较，往前不断挪动位置
2. 运用在array的东西挪到linkedlist上就变得比较麻烦。 但基本思路和array操作一样
3. 有一个优化，直接把tle变成通过，就是每次只当cur的值小于当前head值时，才把cur回移动到最开始

Python

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

class Solution(object):
    # 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
        """
        #something really easy on array become really hard on Linked list!!!
        cur = dummy = ListNode(0) #The returning list, use it to iterate from start each time
        while head:
            if cur and cur.val > head.val: # Added a line to do the optmization
                cur = dummy # The "pre" pointer will help us find out the right position
            while cur.next and cur.next.val < head.val: #move the pre pointer to find the right place
                cur = cur.next
            
            cur.next, cur.next.next, head = head, cur.next, head.next
        return dummy.next