菜鸡的笔试记录

第一题

将链表节点便利，先头插再尾插

class Solution {
public:
    ListNode* formatList(ListNode* head) {
        ListNode* dummy = new ListNode(-1);

        ListNode* ptr = head;
        ListNode* flagtail = head;

        while (ptr != nullptr && ptr->next != nullptr) {
            ListNode* h = ptr;        // 待插入到头
            ListNode* t = ptr->next;  // 待插入到尾
            ListNode* nexthead = ptr->next->next;
            // 头插
            h->next = nullptr;
            h->next = dummy->next;
            dummy->next = h;
            // 尾插
            t->next = nullptr;
            t->next = flagtail->next;
            flagtail->next = t;

            flagtail = t;  // 更新链表尾部标志
            ptr = nexthead;
        }
        // 仅剩一个节点情况的处理
        if (ptr != nullptr) {
            ptr->next = dummy->next;
            dummy->next = ptr;
        }
        return dummy->next;
    }
};

测试用例

1 2 3 4 5  -->  5 3 1 2 4
1 2 3 4 5 6  --> 5 3 1 2 4 6

思路

需要记录每次插入操作的链表结尾的前一个节点，以供尾插时使用，用一个变量记录就好。暴力loop寻找尾结点会超时。

第二题

链表有重复元素，按照已有key的升序排序链表

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

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        map<int, int> dict;

        ListNode* ptr = head;
        int num = 0;

        while (ptr != nullptr) {
            dict[ptr->val] += 1; // 计数
            ptr = ptr->next;
            ++num;
        }
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;

        while (num) {
            for (auto item : dict) {
                if (item.second > 0) {
                    p->next = new ListNode(item.first); // 重建链表
                    dict[item.first] = item.second - 1; // 修改剩余计数
                    p = p->next;
                    --num;
                }
            }
        }
        return dummy->next;
    }
};

测试用例

3 2 3 1 1 3  -->  1 2 3 1 3 3
2 1 2 1 3   --> 1 2 3 1 2

思路

统计链表中元素的出现次数，很适合使用字典存储，可以考虑使用 std::map kv结构，而且底层使用红黑树，按照iter++ 的方式输出就是有序序列，不用对字典排序了。按照元素的个数重建链表就 OK。

第三题（）

看了一眼和LRU题型差不多，没时间写了