面试题：C++插入排序在链表中的应用

Question

给定一个用C++实现的单链表结构，要求使用插入排序算法对链表进行排序，给出链表节点定义及完整的插入排序函数代码，分析该算法的时间和空间复杂度。

Answer 1

链表节点定义

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

插入排序函数代码

ListNode* insertionSortList(ListNode* head) {
    if (head == nullptr) {
        return head;
    }
    ListNode dummy(0);
    dummy.next = head;
    ListNode *pre = &dummy;
    ListNode *cur = head;
    while (cur != nullptr && cur->next != nullptr) {
        if (cur->next->val < cur->val) {
            while (pre->next != nullptr && pre->next->val < cur->next->val) {
                pre = pre->next;
            }
            ListNode *tmp = cur->next;
            cur->next = cur->next->next;
            tmp->next = pre->next;
            pre->next = tmp;
            pre = &dummy;
        } else {
            cur = cur->next;
        }
    }
    return dummy.next;
}

时间复杂度分析

• 插入排序需要遍历链表中的每一个节点，对于每一个节点，在最坏情况下，需要遍历到链表头部来找到合适的插入位置。
• 假设链表长度为 $n$，对于第一个节点，最多比较 $1$ 次；对于第二个节点，最多比较 $2$ 次；以此类推，对于第 $n$ 个节点，最多比较 $n - 1$ 次。
• 总的比较次数为 $1 + 2 + \cdots + (n - 1) = \frac{n(n - 1)}{2}$，所以时间复杂度为 $O(n^2)$。

空间复杂度分析

• 算法中只使用了常数级别的额外空间，例如 dummy 节点、几个指针变量（pre、cur、tmp）等。
• 因此空间复杂度为 $O(1)$。