用户登录
用户注册

分享至

对链表进行插入排序(Python)

  • 作者: Black66506319
  • 来源: 51数据库
  • 2021-09-20

1、题目描述

https://leetcode-cn.com/problems/insertion-sort-list/

对链表进行插入排序。

插入排序算法:

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

2、代码详解

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        dummy = ListNode(0)
        dummy.next = head
        last_sorted = head  # 已排序部分的最后一个节点
        cur = head.next  # 待插入的

        while cur:
            if last_sorted.val <= cur.val:
                last_sorted = last_sorted.next
            else:
                # 从链表的头节点开始往后遍历链表中的节点,寻找插入 cur 的位置
                prev = dummy
                while prev.next.val <= cur.val:
                    prev = prev.next
                # 插入操作:令 prev 为插入 cur 的位置的前一个节点
                last_sorted.next = cur.next
                cur.next = prev.next
                prev.next = cur
            cur = last_sorted.next
        return dummy.next

时间复杂度:O(n*n)

https://leetcode-cn.com/problems/insertion-sort-list/solution/dui-lian-biao-jin-xing-cha-ru-pai-xu-by-leetcode-s/

软件
前端设计
程序设计
Java相关