原題
用插入排序對鏈表排序
樣例
Given 1->3->2->0->null, return 0->1->2->3->null
解題思路
- 寫一個helper函數(shù)霜威，根據(jù)一個head和一個Node，可以將Node插入到一段linked list中升序排列的正確位置
- 一個current指針來遍歷要排序的鏈表，需要記錄一個last值堰汉，否則會超時
- 如果current >= last，current繼續(xù)前進
- 如果current < last拳话，利用helper函數(shù)把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
