对链表进行插入排序

[编程题]对链表进行插入排序

热度指数：1646 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对链表进行插入排序，

从链表第一个元素开始可以视为部分已排序，每次操作从链表中移除一个元素，然后原地将移除的元素插入到已排好序的部分。

数据范围：链表长度满足 $1 \le n \le 1000\$ ，链表中每个元素满足 $|val| \le 10000 \$

例如输入{2,4,1}时，对应的返回值为{1,2,4}，转换过程如下图所示：

示例1

输入

{1,2,3}

输出

{1,2,3}

示例2

输入

{2,4,1}

输出

{1,2,4}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Python3

liangzhengjie

# 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
        res = ListNode(0)

        point = head
        while point is not None:
            point_next = point.next

            insert = res
            while insert is not None:
                if insert.next is None:
                    insert.next = point
                    point.next = None
                    break

                # 寻找插入位置
                if point.val > insert.next.val:
                    insert = insert.next
                    continue
                else:
                    tmp = insert.next
                    insert.next = point
                    point.next = tmp
                    break

            point  = point_next

        return res.next

发表于 2024-04-15 23:18:24 回复(0)