147. 对链表进行插入排序(中)

• 题目
• 题解
• 优化

题目

• 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

  插入排序 算法的步骤:

• 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

• 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

• 重复直到所有输入数据插入完为止。

题解

• 创建一个新链表用于存储排序好的结果，对题目告知的原链表一个一个取节点，进行判断，放到新链表

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)  # 创建哑节点作为新链表的头部
        i = head  # 从原链表的头部开始遍历
        j = dummy  # 新链表的指针
        while i is not None:
            next_node = i.next  # 记录下一个节点，以便继续遍历新链表
            # 在新链表中找到适当的位置插入节点i
            while j.next is not None and j.next.val < i.val:
                j = j.next
            # 将节点i插入到新链表中
            i.next = j.next
            j.next = i
            i = next_node  # 更新i为下一个节点，继续遍历链表1
            j = dummy  # 将j重置为新链表的头部
        return dummy.next  # 返回排序好的新链表

优化

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        # 找个排头
        dummy = ListNode(float("-inf"))
        pre = dummy
        tail = dummy
        # 依次拿head节点
        cur = head
        while cur:
            #因为测试案例很多是有序的，尾指针可以避免从头开始，所以会快很多，这里就是优化所在
            if tail.val < cur.val:#当原链表的值大于新链表尾节点值时，直接插在新链表尾部
                tail.next = cur
                tail = cur
                cur = cur.next
            else:#当原链表的值小于新链表尾节点，需要从新链表头开始找到它插入的位置
                tmp = cur.next # 把下一次节点保持下来，方便更新
                # 找到插入的位置
                while pre.next and pre.next.val < cur.val:
                    pre = pre.next
                # 进行插入操作
                cur.next = pre.next
                pre.next = cur
                pre= dummy#pre重置为新链表的头部
                cur = tmp#更新cur
        tail.next=None#最后记得把尾指针指向空
        return dummy.next