2023-03-07 leetcode写题记录

• 2023-03-07 leetcode写题记录
  • 148. 排序链表
    • 题目链接
    • 题意
    • 解法
      • 归并排序
  • 56. 合并区间
    • 题目链接
    • 题意
    • 解法

复健中，第一次重新写链表题。写链表题需要注意下面这些事项：

1. 写链表时，可以把链表理解成一个数，只不过这个数有特殊含义，代表着一个地址；
2. "->"是对地址对应的对象进行的操作；
3. 在写函数时，指针也有是否引用之分（按一个数去理解就好理解了）。

148. 排序链表

题目链接

148. 排序链表

题意

给你链表的头结点head，请将其按升序排列并返回排序后的链表。

链表定义如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

解法

归并排序

可以自底向上归并排序，这样可以做到空间复杂度为\(O(1)\)，时间复杂度\(O(nlogn)\)。先把各个点都分隔开，即把next值都置为nullptr，然后分层按大小顺序安排next即可。

class Solution {
   public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) return head;
        int n = 0;
        ListNode* tmp = head;
        while (tmp != nullptr) {
            n++;
            tmp = tmp->next;
        }
        ListNode *l = head, *r = head, *ll = l;
        for (int i = 1; i <= n / 2 - 1; ++i) r = r->next, ll = ll->next;
        r = r->next;
        ll->next = nullptr;
        if (n == 1) return head;
        l = sortList(l);
        r = sortList(r);
        ListNode *last = nullptr;
        while (l != nullptr || r != nullptr) {
            if (last == nullptr) {
                fun1(last, pd(l, r));
                tmp = last;
                continue;
            }
            fun2(last, pd(l, r));
        }
        return tmp;
    }

    // 把x变成y，y变成下一个点的地址
    void fun1(ListNode*& x, ListNode*& y) {
        x = y;
        y = y->next;
    }

    // 让x变成y，再把x变成y，y变成下一个点的地址
    void fun2(ListNode*& x, ListNode*& y) {
        x->next = y;
        fun1(x, y);
    }

    // 判断当前x该变成哪个值
    ListNode*& pd(ListNode*& x, ListNode*& y) {
        if (x == nullptr || (y != nullptr && x->val > y->val)) return y;
        return x;
    }
};

56. 合并区间

题目链接

56. 合并区间

题意

以数组\(intervals\)表示若干个区间的集合，其中单个区间为\(intervals[i] = [start_i, end_i]\)。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

解法

class Solution {
   public:
    vector<vector<int>> merge(vector<vector<int>>& a) {
        sort(a.begin(), a.end(), [](vector<int>& x, vector<int>& y) {
            return x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]);
        });
        vector<vector<int>> ans;
        for (vector<int>& x : a)
            if (ans.empty() || ans.back()[1] < x[0])
                ans.push_back(x);
            else
                ans.back()[1] = max(ans.back()[1], x[1]);
        return ans;
    }
};