本文源自于个人github仓库：https://github.com/forthespada/InterviewGuide
github仓库内有PDF版本笔记下载方式，欢迎各位star、fork~
立志收录计算机校招、社招面试最全面试，无内鬼来点八股文~
八股文：一般指的就是面试中常问问题，固定回答的问题，比如常见的进程线程区别、TCP三次握手四次挥手等

说实话，算法这种东西没得快速提升，算法能力的提升需要日积月累慢慢累积而成的。

在互联网招聘中，不管是笔试还是面试中的手撕算法，可以考察的算法题简直不要太多。比如链表、树、数组、动态规划、回溯算法、贪心算法、甚至是拓扑都有可能考察到。

而一般说来笔试的难度是比面试稍微高一些的，面试中的手撕算法难度一般是力扣的 medium 水平，也有一些 easy 的，而笔试至少都是力扣 medium 难度以上的。

我仅在这章节中为大家盘点一下互联网大厂面试考察频率比较高的几道手撕算法题，希望我的整理对大家有一点点用处，那我就很高兴了！。

1、合并有序链表

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

力扣链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

#include <iostream>
using namespace std;

struct myList {
    int val;
    myList* next;
    myList(int _val) :val(_val), next(nullptr) {}
};

myList* merge(myList* l1, myList* l2) {

    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    myList head(0);
    myList* node = &head;
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            node->next = l1;
            l1 = l1->next;

        }
        else {
            node->next = l2;
            l2 = l2->next;
        }
        node = node->next;
    }

    if (l1 == nullptr)
        node->next = l2;
    if (l2 == nullptr)
        node->next = l1;

    return head.next;

};

int main(void) {

    myList* node0 = new myList(0);
    myList* node1 = new myList(1);
    myList* node2 = new myList(2);
    myList* node3 = new myList(3);

    myList* node4 = new myList(1);
    myList* node5 = new myList(4);
    node0->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = nullptr;
    node4->next = node5;
    node5->next = nullptr;

    auto node = merge(node0, node4);
    while (node != nullptr) {
        cout << node->val << endl;
        node = node->next;
    }

    return 0;
}

2、反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

第一种做法

#include<algorithm>
#include<unordered_map>
#include <iostream>
#include<vector>

using namespace std;

struct node {
    int  data;
    struct node* next;
    node(int _data) :data(_data), next(nullptr) {
    }
};

struct node* init() {
    node* head = new node(1);
    node* node1 = new node(2);
    node* node2 = new node(3);
    node* node3 = new node(4);
    node* node4 = new node(5);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = nullptr;

    return head;
}

struct node* reverse(node* head) {
    struct node* pre =