0147. 对链表进行插入排序

0147. 对链表进行插入排序 #

  • 标签:链表、排序
  • 难度:中等

题目大意 #

描述:给定链表的头节点 head

要求:对链表进行插入排序。

说明

  • 插入排序算法:
    • 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
    • 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
    • 重复直到所有输入数据插入完为止。
  • 列表中的节点数在 $[1, 5000]$ 范围内。
  • $-5000 \le Node.val \le 5000$。

示例

1
2
输入: head = [4,2,1,3]
输出: [1,2,3,4]

1
2
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

解题思路 #

思路 1:链表插入排序 #

  1. 先使用哑节点 dummy_head 构造一个指向 head 的指针,使得可以从 head 开始遍历。

  2. 维护 sorted_list 为链表的已排序部分的最后一个节点,初始时,sorted_list = head

  3. 维护 prev 为插入元素位置的前一个节点,维护 cur 为待插入元素。初始时,prev = headcur = head.next

  4. 比较 sorted_listcur 的节点值。

    • 如果 sorted_list.val <= cur.val,说明 cur 应该插入到 sorted_list 之后,则将 sorted_list 后移一位。
    • 如果 sorted_list.val > cur.val,说明 cur 应该插入到 headsorted_list 之间。则使用 prevhead 开始遍历,直到找到插入 cur 的位置的前一个节点位置。然后将 cur 插入。
  5. cur = sorted_list.next,此时 cur 为下一个待插入元素。

  6. 重复 4、5 步骤,直到 cur 遍历结束为空。返回 dummy_head 的下一个节点。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        dummy_head = ListNode(-1)
        dummy_head.next = head
        sorted_list = head
        cur = head.next 
        
        while cur:
            if sorted_list.val <= cur.val:
                # 将 cur 插入到 sorted_list 之后
                sorted_list = sorted_list.next 
            else:
                prev = dummy_head
                while prev.next.val <= cur.val:
                    prev = prev.next
                # 将 cur 到链表中间
                sorted_list.next = cur.next
                cur.next = prev.next
                prev.next = cur
            cur = sorted_list.next 
        
        return dummy_head.next

思路 1:复杂度分析 #

  • 时间复杂度:$O(n^2)$。
  • 空间复杂度:$O(1)$。
本站总访问量  次  |  您是本站第  位访问者