对链表进行插入排序

发表于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

LeetCode每日一题，147. Insertion Sort List

先看题目描述

DQmQr6.png

大意就是使用插入排序对链表进行排序

算法和思路

插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 1，直到全部元素都加入到有序序列中

若是数组的插入排序，则每次从后往前寻找插入位置，并将插入位置之后的元素都向后移一位即可；题目中是链表的插入排序，而每个节点指向的都是其后一个节点，所以我们每次要从前往后寻找插入位置，然后将当前节点插入到该位置即可，就这样不断维护前面的有序链表

算法流程

  • 初始化一个哑节点 dump， 使其值为整数最小值，next 指向 head；定义一个指针 tail 指向当前有序链表的尾部，初始化其指向 head；初始化一个指针 cur = head.next，用于遍历链表的未排序部分
  • 移动 cur 来遍历链表的未排序部分：
    • 若 tail.val <= cur.val：
      • 说明 cur 应插入到目前有序链表的尾部，令 tail = cur
    • 若 tail.val > cur.val，则从前往后寻找 cur 应插入的位置：
      • 初始化指针 temp = dump.next，prev = dump
      • 移动 prev 和 temp 指针，令 prev = temp，temp = temp.next 直至 temp.val > cur.val
      • 此时 prev 指针就指向 cur 应插入位置的前一个节点，将 cur 插入到 prev 和 temp 之间，令 tail.next = cur.next，prev.next = cur，cur.nex = temp
    • 移动 cur 指针使其指向未排序链表的第一个元素，令 cur = tail.next
  • 最后返回 dump.next

算法源码

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
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return null;
        ListNode dump = new ListNode(Integer.MIN_VALUE);
        dump.next = head;
        ListNode tail = head;
        ListNode cur = tail.next;
        while (cur != null) {
            if (tail.val <= cur.val) {
                tail = cur;
            } else {
                ListNode temp = dump.next;
                ListNode prev = dump;
                while (temp.val <= cur.val) {
                    prev = temp;
                    temp = temp.next;
                }
                tail.next= cur.next;
                prev.next = cur;
                cur.next = temp;
            }
            cur = tail.next;
        }
        return dump.next;
    }
}