python实现leetcode之147. 对链表进行插入排序

解题思路

使用一个虚拟节点作为头节点，代码会被极大的优化

147. 对链表进行插入排序

代码

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

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        rtv = ListNode(0)
        while head:
            nx = head.next
            pt = rtv
            while pt.next and pt.next.val < head.val:
                pt = pt.next
            head.next = pt.next
            pt.next = head
            head = nx
        return rtv.next