leetcode-147

147. 对链表进行插入排序

从第一个元素开始，该链表可以被认为已经部分排序。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

• 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
• 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
• 重复直到所有输入数据插入完为止。

示例

输入: 4->2->1->3
输出: 1->2->3->4

输入: -1->5->3->4->0
输出: -1->0->3->4->5

题解

解法一：

先将链表中的相邻元素依次比较，如果出现前面的大于后面的则暂停，记录当前需要插入的元素。

然后从头开始寻找需要插入的位置。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode,n=5) -> ListNode:
        dummy = ListNode(val=float("-inf"),next=head)

        bound = dummy.next
        while True :
            
            cur = bound

            # 找到cur后面的元素不大于它的元素
            while cur.next and  cur.val <=cur.next.val :
                cur = cur.next
          
            
            # cur后面的元素小于它自己，此时需要插入    
            need_insert = cur.next if cur.next else None
            if not need_insert: break
 
            # 从头结点开始寻找合适的插入位置
            insert_pre = dummy
            while insert_pre.next.val < need_insert.val:
                insert_pre = insert_pre.next   
            
            # 接上后面的
            cur.next = need_insert.next

            # 接上前面的
            need_insert.next = insert_pre.next
            insert_pre.next = need_insert
            bound = need_insert
          
        return  dummy.next