题目
Sort a linked list using insertion sort.
思路
这道题花费了最多的时间。
- 复习了array的插入排序，用两个循环实现，每次循环到下一个数，和之前的比较，往前不断挪动位置
- 运用在array的东西挪到linkedlist上就变得比较麻烦。 但基本思路和array操作一样
- 有一个优化，直接把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
