这周台风停了两天课，实训和数据结构也没布置习题，所以基本只做了力扣（还因为数据结构大作业搁置了一天）。

力扣

随机链表的复制

很有意思一道题，有一个随机跳转的链表，要求你进行深拷贝。这题的坑在于深拷贝不允许破坏原链表结构，所以如果你对原链表进行了操作你最后必须得复原。

这题的思路就是先把原链表的每个节点拆成两个相邻的节点，这样可以保证你在深拷贝随机指针的时候，也可以维持原结构。

$A \rarr B \rarr C \Rarr A^{\prime} \rarr B^{\prime} \rarr C^{\prime}$

第一步：拆分

if (head == nullptr) return nullptr;
    Node *p = head;
while (p != nullptr) {
    Node *temp = new Node(p->val);
    temp->random = p->random;
    temp->next = p->next;
    p->next = temp;
    p = p->next->next;
}

第二步：复制random指针

p = head;
Node *ans = head->next;
while (p != nullptr) {
    if (p->random != nullptr && p != nullptr)
        p->next->random = p->random->next;
    p = p->next->next;
}

第三步：拆离并复原

p = head;
while (p->next->next != nullptr) {
    Node *temp = p->next->next;
    p->next->next = p->next->next->next;
    p->next = temp;
    p = p->next;
}
p->next = nullptr; //这一步是将最后一个节点复原，因为循环reach不到

排序链表

练习归并排序极佳的机会，而且链表其实比数组容易实现的多，缺点就是找中间指针比较费劲需要用到双指针法。

题目没有要求返回的链表要是原链表，所以我们可以随意一点。

先写排序部分

ListNode* mergeSort(ListNode *begin, ListNode *end) {
    if (begin == nullptr) return begin;
    if (begin->next == end) {
        begin->next = nullptr;
        return begin;
    }
    ListNode *fast = begin;
    ListNode *slow = begin;
    while (fast != end) {
        slow = slow->next;
        fast = fast->next;
        if (fast != end) {
            fast = fast->next;
        }
    }
    ListNode *mid = slow;
    return merge(mergeSort(begin, mid), mergeSort(mid,end));

这个双指针找法比别的好，既优美（不用多写个flag）又保证了当链表长度为奇数时找到的是中值。

当链表长度为1或0时，直接返回头结点即可，到时候去跟另外一个链表做归并。

下面写归并的函数

ListNode* merge(ListNode *begin, ListNode *mid) {
    ListNode *dummy = new ListNode();
    ListNode *ans = dummy;
    ListNode *L = begin, *R = mid;
    while (L != nullptr && R != nullptr) {
        if (L->val <= R->val) {
            dummy->next = L;
            L = L->next;
        } else {
            dummy->next = R;
            R = R->next;
        }
        dummy = dummy->next;
    }
    if (L != nullptr) {
        dummy->next = L;
    } else if (R != nullptr) {
        dummy->next = R;
    }
    return ans->next;
}

经典的建立dummy节点，让操作变的十分方便。最后我们只需要对想排序的链表使用mergeSort(head, nullptr)即可。

杂项

删除链表重复项的算法

我当然知道用hashmap很方便，但是老师大概率不让用。所以这里实现一个时间复杂度为$O(n^2)$的算法。

void removeDuplicates(Node* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    
    Node* current = head;
    
    while (current != NULL && current->next != NULL) {
        Node* runner = current;
        
        while (runner->next != NULL) {
            if (runner->next->data == current->data) {
                Node* temp = runner->next;
                runner->next = runner->next->next;
                free(temp);
            } else {
                runner = runner->next;
            }
        }
        current = current->next;
    }
}

时间复杂度确实有点爆炸。

贪吃蛇的实现

我这里指的不是一整个游戏，仅仅是蛇本身。蛇需要移动，假设我们已经实现了控制头移动的方向，如何让身体每个部分都跟随自己的上一部分移动呢？

我们需要一个合适的数据结构，而答案十分的形象：长得最像蛇形的数据结构——链表。

先实现身体的每个部分

struct SnakeBody {
    int x, y;
    bool is_head;
}

然后直接使用cpp模板库里的链表，即std::List<SnakeBody> SnakeList，这样我们蛇移动时，只需要先移动头，然后把身体每个部分的下一个节点移到上一个节点的位置即可。

假设我们已经移动过蛇头了

auto it = SnakeList.begin();
auto prevX = it->x, prevY = it->y;
it++; // 直接跳过蛇头
while (it != SnakeList.end()) {
    int tempX = it->x, tempY = it->prev->y;
    it->x = prevX;
    it->y = prevY;
    prevX = tempX;
    prevY = tempY;
}

多项式解析器

数据结构课大作业，我用Dijkstra双栈算法实现了一个用来合并多项式的工具。之后可能会发上Github，这里不细说，只讲Dijkstra双栈算法。

Dijkstra双栈算法就是利用两个栈，分别存放运算符和数字，来实现表达式的保证了括号和其他运算符优先级正确的求值。

我们需要维护一个运算符优先级的表std::map<char, int> op_preced

假设我们读取到了字符串std::string expr; std::cin >> expr，我们现在对其进行解析。

std::stack<char> ops;
std::stack<int> nums;

for (auto it = expr.begin(); it != expr.end(); it++) {
    if (*it == ' ') continue;
    if (std::isdigit(*it)) {
        // 碰到数字了，就向右吸取所有的数字。
        int number = *it - '0';
        while (it != expr.end() && std::isdigit(*it)) {
            number = number * 10 + *it;
        }
        nums.push(number); // 先将数字压入栈中。
    } else if (op_preced.contains(*it)) { // 你得保证这个运算符是有效的吧
        // 现在我们要开始进行计算了，但为了保证运算符优先级顺序，
        // 我们要先把栈顶优先级比(*it)大的运算符先提出来计算了，才能把(*it)压入栈中。
        while (!ops.empty() && op_preced.contains(ops.top()) && op_preced[ops.top()] >= op_preced[*it]) {
            apply_operator(nums, ops);
        }
    } else if (*it == '(') {
        // 碰到左括号了，直接压入栈中即可
        ops.push('(');
    } else if (*it == ')') {
        // 遇到右括号说明现在要先把栈中左括号后的内容都计算完
        while (!ops.empty() && ops.top() != '(') {
            apply_operator(nums, ops);
        };
        // 然后弹出左括号
        ops.pop();
    }
}
// 把剩下的执行完
while (!ops.empty()) apply_operator(nums.ops);
// 最后数字栈顶就是我们的结果。
int ans = nums.top();

现在实现一下apply_operator函数，用于栈中数字的运算

void apply_operator(std::stack<int> nums, std::stack<char> ops) {
    if (ops.empty()) return;

    char op = ops.top();ops.pop();
    auto right = nums.top();nums.pop();
    auto left = nums.top();nums.pop();

    // 然后在下面执行 left op right 即可，用switch语句很方便
    int result;
    // result = left op right;
    // 最后将结果压入栈中用于之后的运算。
    nums.push(result);
}