說實話，算法這種東西沒得快速提升，算法能力的提升需要日積月累慢慢累積而成的。

在互聯(lián)網(wǎng)招聘中，不管是筆試還是面試中的手撕算法，可以考察的算法題簡直不要太多。比如鏈表、樹、數(shù)組、動態(tài)規(guī)劃、回溯算法、貪心算法、甚至是拓撲都有可能考察到。

而一般說來筆試的難度是比面試稍微高一些的，面試中的手撕算法難度一般是力扣的 medium 水平，也有一些 easy 的，而筆試至少都是力扣 medium 難度以上的。

我僅在這章節(jié)中為大家盤點一下互聯(lián)網(wǎng)大廠面試考察頻率比較高的幾道手撕算法題，希望我的整理對大家有一點點用處，那我就很高興了！。

1、合并有序鏈表

將兩個有序的鏈表合并為一個新鏈表，要求新的鏈表是通過拼接兩個鏈表的節(jié)點來生成的。

輸入：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、反轉(zhuǎn)鏈表

定義一個函數(shù)，輸入一個鏈表的頭節(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點。

輸入: 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 = new node(-1);
    struct node* temp = new node(-1);
    pre = head;
    temp = head->next;
    pre->next = nullptr;    
    struct node* cur = new node(-1);
    cur = temp;
    while (cur != nullptr) {
        temp = cur;
        cur = cur->next;
        temp->next = pre;
        pre = temp;
    }

    return pre;
}

int main(){
    auto head = init();
    head = reverse(head);
    while (head != nullptr) {
        cout << head->data << endl;
        head = head->next;
    }

    return 0;
}

第二種做法

//頭插法來做，將元素開辟在棧上，這樣會避免內(nèi)存泄露
ListNode* ReverseList(ListNode* pHead) {

    // 頭插法
    if (pHead == nullptr || pHead->next == nullptr) return pHead;
    ListNode dummyNode = ListNode(0);
    ListNode* pre = &(dummyNode);
    pre->next = pHead;
    ListNode* cur = pHead->next;
    pHead->next = nullptr;
    //pre = cur;
    ListNode* temp = nullptr;
    while (cur != nullptr) {
        temp = cur;
        cur = cur->next;
        temp->next = pre->next;
        pre->next = temp;
    }
    return dummyNode.next;

}

3、單例模式

餓漢模式

class singlePattern {
private:
    singlePattern() {};
    static singlePattern* p;
public:
    static singlePattern* instance();

    class CG {
    public:
        ~CG() {
            if (singlePattern::p != nullptr) {
                delete singlePattern::p;
                singlePattern::p = nullptr;
            }
        }
    };
};

singlePattern* singlePattern::p = new singlePattern();
singlePattern* singlePattern::instance() {
    return p;
}

update1: instance 手誤寫成 instacne，微信好友“卷軸”提出，已修正，感謝！- 20210407

懶漢模式

class singlePattern {
private:
    static singlePattern* p;
    singlePattern(){}
public:
    static singlePattern* instance();
    class CG {
    public:
        ~CG() {
            if (singlePattern::p != nullptr) {
                delete singlePattern::p;
                singlePattern::p = nullptr;
            }
        }
    };
};
singlePattern* singlePattern::p = nullptr;
singlePattern* singlePattern::instance() {
    if (p == nullptr) {
        return new singlePattern();
    }
    return p;
}

4、簡單工廠模式

typedef enum productType {
    TypeA,
    TypeB,
    TypeC
} productTypeTag;

class Product {

public:
    virtual void show() = 0;
    virtual ~Product() = 0;
};

class ProductA :public Product {
public:
    void show() {
        cout << "ProductA" << endl;
    }
    ~ProductA() {
        cout << "~ProductA" << endl;
    }
};

class ProductB :public Product {
public:
    void show() {
        cout << "ProductB" << endl;
    }
    ~ProductB() {
        cout << "~ProductB" << endl;
    }
};

class ProductC :public Product {
public:
    void show() {
        cout << "ProductC" << endl;
    }
    ~ProductC() {
        cout << "~ProductC" << endl;
    }
};

class Factory {

public:
    Product* createProduct(productType type) {
        switch (type) {
        case TypeA:
            return new ProductA();
        case TypeB:
            return new ProductB();
        case TypeC: