题解 | #对链表进行插入排序#

插入排序思想,当前值 <= val 时继续迭代,直到遇到较大值,由于链表结构,需要重置 next 节点,若是数组要进行移位操作

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def insertionSortList(self , head: ListNode) -> ListNode:
        # write code here
        pre = ListNode(-1)
        while head:
            pre2 = pre
            while pre2.next and pre2.next.val <= head.val:
                pre2 = pre2.next
            t = pre2.next
            pre2.next = head
            n = head.next
            head.next = t
            head = n
        return pre.next