原题
用插入排序对链表排序
样例
Given 1->3->2->0->null, return 0->1->2->3->null
解题思路
- 写一个helper函数，根据一个head和一个Node，可以将Node插入到一段linked list中升序排列的正确位置
- 一个current指针来遍历要排序的链表，需要记录一个last值，否则会超时
- 如果current >= last，current继续前进
- 如果current < last，利用helper函数把current插入到前面
完整代码
# 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
"""
if not head:
return head
dummy = ListNode(0)
dummy.next = head
last = head.val
while head.next != None:
if head.next.val >= last:
last = head.next.val
head = head.next
else:
self.insert(dummy, ListNode(head.next.val))
head.next = head.next.next
return dummy.next
def insert(self, head, node):
while head.next != None and head.next.val <= node.val:
head = head.next
node.next = head.next
head.next = node
