daily_leetcode_2020_1120_147_对链表进行插入排序

1 题目描述

对链表进行插入排序。

插入排序算法：

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

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

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

2 题解

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:

        """
        在链表的题目中，无论是增删改查，增加哑节点是一个非常好的编程习惯，特别是在节点删除的时候能起到非常重要的作用
        在遍历排序中，不至于让我们丢掉了头节点


        我们需要一个while循环去遍历链表{

                每次比较 相邻的两个节点值的大小，如果是升序的那就没有不要操作了，链表前进一步，继续取两个比较

                如果不是，那么我们就要 将后面这个节点插入到 前面已经有序的链表中，
                那么怎么插呢，那必须得从 前面已经有序的链表 从头开始比较大小， 找的合适它得位置(所以这里也得一个while循环)

                将其插入（常规操作)
                插入之后呢，是不是得回到原先遍历得位置， 继续遍历

        }


        """

        # jdi147.com 哑节点
        dummy = ListNode(float("inf"))
        dummy.next = head

        while head and head.next:

            if head.val <= head.next.val:
                head = head.next
            else:
                """ 寻找待插入节点 的 合适位置， pre为待插位置的前驱节点 """
                pre = dummy
                while pre.next.val < head.next.val:
                    pre = pre.next

                insert = head.next
                head.next = head.next.next  # jdi147.com insert被插到前面去了，所以head得跳过insert连接到下一个节点
                insert.next = pre.next
                pre.next = insert

        return dummy.next