题目描述：

Sort a linked list using insertion sort.

题目大意：

使用插入排序对链表排序。

Python代码：

朴素版本（ Accepted 2568ms )：

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

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        dummyNode = ListNode(0)
        current = head
        while current is not None:
            next = current.next
            current.next = None
            p = dummyNode
            while p is not None:
                if p.next is None or current.val < p.next.val:
                    current.next = p.next
                    p.next = current
                    break
                p = p.next
            current = next
        return dummyNode.next

优化版本（ Accepted 316ms )：

参考LeetCode Discuss链接：https://oj.leetcode.com/discuss/7482/one-way-to-accept-in-python-against-tle

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

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if not head:
            return head
        fh = ListNode(0)
        fh.next = head
        cur = head
        while cur.next:
            if cur.next.val < cur.val:
                pre = fh
                while pre.next.val < cur.next.val:
                    pre = pre.next
                t = cur.next
                cur.next = t.next
                t.next = pre.next
                pre.next = t
            else:
                cur = cur.next
        return fh.next

 

本文链接：http://bookshadow.com/weblog/2015/01/06/leetcode-insertion-sort-list/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码