0147. 对链表进行插入排序

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

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

题目大意 #

给定链表的头节点 head

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

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

解题思路 #

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

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

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

  4. 比较 sorted_listcurr 的节点值。

    • 如果 sorted_list.val <= curr.val,说明 curr 应该插入到 sorted_list 之后,则将 sorted_list 后移一位。

    • 如果 sorted_list.val > curr.val,说明 curr 应该插入到 headsorted_list 之间。则使用 prevhead 开始遍历,直到找到插入 curr 的位置的前一个节点位置。然后将 curr 插入:

      • 1
        2
        3
        
        sorted_list.next = curr.next
        curr.next = prev.next
        prev.next = curr
        
  5. curr = sorted_list.next,此时 curr 为下一个待插入元素。

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

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    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
        curr = head.next
        while curr:
            if sorted_list.val <= curr.val:
                sorted_list = sorted_list.next
            else:
                prev = dummy_head
                while prev.next.val <= curr.val:
                    prev = prev.next
                sorted_list.next = curr.next
                curr.next = prev.next
                prev.next = curr
            curr = sorted_list.next
        return dummy_head.next
本站总访问量  次  |  您是本站第  位访问者