一：合并 K 个升序链表

image-20251024155847346

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
26
27
28
29
30
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len = lists.size();
        ListNode* retuslt = nullptr;
        for (int i = 0; i < len; ++i) retuslt = Merge(retuslt, lists[i]);
        return retuslt;
    }
    ListNode* Merge(ListNode* a, ListNode* b)
    {
        if (!a || !b) return a ? a : b;
        ListNode head, *tail = &head;
        while (a && b)
        {
            if (a->val < b->val)
            {
                tail->next = a;
                a = a->next;
            }
            else
            {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return head.next;
    }
};

image-20251024160002923

2. 分治合并

将数组中的链表两两配对，依次递归

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
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return recursion(lists, 0, lists.size() - 1);
    }
    ListNode* recursion(vector<ListNode*>& lists, int left, int right)
    {
        if (left == right) return lists[left];
        if (left > right) return nullptr;
        int mid = (left + right) >> 1;
        return Merge(recursion(lists, left, mid), recursion(lists, mid + 1, right));
    }
    ListNode* Merge(ListNode* a, ListNode* b)
    {
        if (!a || !b) return a ? a : b;
        ListNode head, *tail = &head;
        while (a && b)
        {
            if (a->val < b->val)
            {
                tail->next = a;
                a = a->next;
            }
            else
            {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return head.next;
    }
};

image-20251024155946005

3. 使用优先队列合并

根据节点的值将其放入优先队列中，依次取出队列顶端的值，可得到最小的节点

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
class Solution {
public:
    struct Node
    {
        int val;
        ListNode* p;
        bool operator < (const Node &com) const
        {
            return val > com.val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode head, *cur = &head;
        priority_queue<Node> pq;
        for (auto &list : lists) 
            if (list) pq.push({list->val, list});
        while (!pq.empty())
        {
            auto temp = pq.top();
            pq.pop();
            cur->next = temp.p;
            cur = cur->next;
            if (temp.p->next) pq.push({temp.p->next->val, temp.p->next});
        }
        return head.next;
    }

};

image-20251024155937939

二：K 个一组翻转链表

image-20251024160045745

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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* result = new ListNode(0);
        result->next = head;
        ListNode* pre = result;
        while (head)
        {
            ListNode* tail = pre;
            for (int i = 0; i < k; ++i)
            {
                tail = tail->next;
                if (tail == nullptr) return result->next;
            }
            ListNode* next = tail->next;
            tie(head, tail) = Reverse(head, tail);
            pre->next = head;
            tail->next = next;
            head = tail->next;
            pre = tail;
        }
        return result->next;
    }
    pair<ListNode*, ListNode*> Reverse(ListNode* head, ListNode* tail)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (pre != tail)
        {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return {tail, head};
    }
};

image-20251024160113853

三：缺失的第一个正数

image-20251024160155986

1. 哈希表

想要记录没有出现的数据，通常使用哈希表，这里无法使用额外空间，我们可以对数组进行原地操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        for (auto& num: nums)
            if (num <= 0) num = INT_MAX;
        for (auto& num: nums)
        {
            int temp = abs(num);
            if (temp <= len) nums[temp - 1] = -abs(nums[temp - 1]);     // 这里可能修改后面的数据，所以取负值
        }
        for (int i = 0; i < len; ++i)
            if (nums[i] > 0) return i + 1;
        return len + 1;
    }
};

image-20251024160223161

2. 置换

我们可以尝试把元素的值与数组索引对应

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len; ++i)
            while (nums[i] > 0 && nums[i] <= len && nums[i] != nums[nums[i] - 1]) 
                swap(nums[i], nums[nums[i] - 1]);
        for (int i = 0; i < len; ++i)
            if (nums[i] != i + 1) return i + 1;
        return len + 1;
    }
};

image-20251024160231490