C++的标准不允许复制构造函数传值参数。A(const A& other){}，如果是传值参数，把形参复制到实参会调用复制构造函数，就会形成无休止的递归调用从而导致栈溢出。

赋值运算符函数

class CMyString
{
public:
    CMyString(char *pData = NULL);
    CMyString(const CMyString& str);
    ~CMyString();
    CMyString& operator=(const CMyString& other);
private:
    char *m_pData;
};

CMyString& CMyString::operator=(const CMyString& other)
{
    if (this == &other)
    {
        return *this;
    }
    delete m_pData;
    m_pData = new char[strlen(other.m_pData) + 1];
    strcpy(m_pData, other.m_pData);
}

合并两个已排序数组，第一个数组足以容纳两个数组的所有元素

int merge(int num1[], int len1, int num2[], int len2)
{
    int i = len1 + len2 - 1;
    int j = len1 - 1;
    int k = len2 - 1;
    while (j >= 0 && k >= 0)
    {
        if (num1[j] > num1[k])
        {
            num1[i--] = num1[j--];
        }
        else
        {
            num1[i--] = num2[k--];
        }
    }
    while (j >= 0)
    {
        num1[i--] = num1[j--];
    }
    while (k >= 0)
    {
        num1[i--] = num2[k--];
    }

    return len1 + len2;
}

链表中删除某个结点

ListNode* deleteNode(ListNode *head, int key)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode *cur = head;
    ListNode *pre;
    ListNode *temp;
    while (cur->val != key)
    {
        pre = cur;
        cur = cur->next;
    }
    temp = cur;
    if (cur == head)
    {
        head = head->next;
    }
    else
    {
        pre->next = cur->next;
    }
    delete temp;

    return head;
}

或

ListNode* deleteNode(ListNode *head, int key)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode *temp;
    if (head->val == key)
    {
        temp = head;
        head = head->next;
    }
    else
    {
        ListNode *p = head;
        while (p->next != NULL && p->next->val != key)
        {
            p = p->next;
        }
        if (p->next != NULL && p->next->val == key)
        {
            temp = p->next;
            p->next = p->next->next;
        }
    }
    delete temp;

    return head;
}

从尾到头打印链表

void print(ListNode *head)
{
    if (head != NULL)
    {
        print(head->next);
        cout<<head->val<<" ";
    }
}

或

void print(ListNode *head)
{
    stack<ListNode*> s;
    while (head != NULL)
    {
        s.push(head);
        head = head->next;
    }
    while (!s.empty())
    {
        cout<<s.top()->val<<" ";
        s.pop();
    }
}

重建二叉树

TreeNode* constructHelp(int *prestart, int *preend, int *instart, int *inend)
{
    int *rootin = instart;
    while (rootin <= inend && *rootin != *prestart)
    {
        ++rootin;
    }
    int leftLen = rootin - instart;
    int rightLen = inend - rootin;
    TreeNode *root = new TreeNode(*prestart);
    if (leftLen > 0)
    {
        root->left = constructHelp(prestart + 1, prestart + leftLen, instart, rootin - 1);
    }
    if (rightLen > 0)
    {
        root->right = constructHelp(prestart + leftLen + 1, preend, rootin + 1, inend);
    }

    return root;
}

TreeNode* construct(int preorder[], int inorder[], int len)
{
    if (preorder == NULL || inorder == NULL || len <= 0)
    {
        return NULL;
    }
    return constructHelp(preorder, preorder + len - 1, inorder, inorder + len - 1);
}

两个栈实现一个队列

template<class T> class MyQueue
{
public:
    void push(T t)
    {
        s1.push(t);
    }

    void pop()
    {
        if (s2.empty())
        {
            gather(s1, s2);
        }
        s2.pop();
    }

    T front()
    {
        if (s2.empty())
        {
            gather(s1, s2);
        }
        return s2.top();
    }

    bool empty()
    {
        return s1.empty() && s2.empty();
    }
private:
    void gather(stack<T> &s1, stack<T> &s2)
    {
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
    }
    stack<T> s1;
    stack<T> s2;
};

两个队列实现一个栈

template<class T> class MyStack
{
public:
    void push(T t)
    {
        if (q1.empty())
        {
            q2.push(t);
        }
        else
        {
            q1.push(t);
        }
    }

    T top()
    {
        T t = leaveOne(q2, q1);
        push(t);

        return t;
    }

    void pop()
    {
        leaveOne(q1, q2);
    }

    bool empty()
    {
        return q1.empty() && q2.empty();
    }
private:
    T leaveOne(queue<T> &q1, queue<T> &q2)
    {
        if (q1.size() == 0)
        {
            swap(q1, q2);
        }
        while (q1.size() > 1)
        {
            q2.push(q1.front());
            q1.pop();
        }
        T t = q1.front();
        q1.pop();

        return t;
    }
    queue<T> q1;
    queue<T> q2;
};

排序员工年龄（假设age>= 0 && age<=99）

void sort(int num[], int len)
{
    int cnt[100] = {0};
    for (int i = 0; i < len; i++)
    {
        cnt[num[i]]++;
    }

    int index = 0;
    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < cnt[i]; j++)
        {
            num[index++] = i;
        }
    }
}

旋转数组的最小数字

int findMinHelp(int num[], int left, int right)
{
    int res = left;
    for (int i = left + 1; i <= right; i++)
    {
        if (num[i] < num[res])
        {
            res = i;
        }
    }
    return res;
}

int findMin(int num[], int len)
{
    int left = 0;
    int right = len - 1;
    int mid = left;
    while (num[left] >= num[right])
    {
        if (right - left == 1)
        {
            mid = right;
            break;
        }
        mid = (left + right) / 2;
        if (num[mid] == num[left] && num[mid] == num[right])
        {
            return findMinHelp(num, left, right);
        }
        if (num[mid] >= num[left])
        {
            left = mid;
        }
        else if (num[mid] <= num[right])
        {
            right = mid;
        }
    }
    return mid;
}

三种错误处理方式优缺点比较

打印1到最大的n位数

void print(int num[], int len)
{
    bool flag = false;
    int index;
    for (int i = 0; i < len; i++)
    {
        if (num[i] != 0)
        {
            index = i;
            flag = true;
            break;
        }
    }
    if (flag)
    {
        for (int i = index; i < len; i++)
        {
            cout<<num[i];
        }
        cout<<" ";
    }
}

void fun(int num[], int len, int pos)
{
    for (int i = 0; i < 10; i++)
    {
        num[pos] = i;
        if (pos == len - 1)
        {
            print(num, len);
        }
        else
        {
            fun(num, len, pos + 1);
        }
    }
}

在O(1)时间内删除链表结点

ListNode* deleteNode(ListNode *head, ListNode *del)
{
    if (head == NULL || del == NULL)
    {
        return head;
    }
    if (del->next != NULL)
    {
        ListNode *temp = del->next;
        del->val = temp->val;
        del->next = temp->next;
        delete temp;
    }
    else if (del == head)
    {
        delete head;
        head == NULL;
    }
    else
    {
        ListNode *p  = head;
        while (p->next != del)
        {
            p = p->next;
        }
        p->next = del->next;
        delete del;
    }

    return head;
}

调整数组顺序使奇数位于偶数前面

void fun(int num[], int len)
{
    if (num == NULL)
    {
        return;
    }
    int i = 0;
    int j = len - 1;
    while (i < j)
    {
        while (i < j && num[i] & 0x1)
        {
            i++;
        }
        while (i < j && !(num[j] & 0x1))
        {
            j--;
        }
        swap(num[i++], num[j--]);
    }
}

此处有一种扩展方法，将第二个和第三个while的判断条件写成一个函数，然后为主函数增加一个参数，该参数为一个函数指针。

链表中倒数第K个结点

ListNode* findKth(ListNode *head, int k)
{
    if (head == NULL || k == 0)
    {
        return NULL;
    }
    ListNode *p1 = head;
    for (int i = 0; i < k - 1; i++)
    {
        if (p1->next != NULL)
        {
            p1 = p1->next;
        }
        else
        {
            return NULL;
        }
    }
    ListNode *p2 = head;
    while (p1->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }

    return p2;
}

反转链表

ListNode* reverse(ListNode *head)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode *pre = head;
    ListNode *cur = head->next;
    while (cur != NULL)
    {
        pre->next = cur->next;
        cur->next = head;
        head = cur;
        cur = pre->next;
    }

    return head;
}

ListNode* reverse2(ListNode *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    ListNode *newhead = reverse2(head->next);
    head->next->next = head;
    head->next = NULL;

    return newhead;
}

合并两个排序的链表

ListNode* merge(ListNode *head1, ListNode *head2)
{
    if (head1 == NULL)
    {
        return head2;
    }
    else if (head2 == NULL)
    {
        return head1;
    }
    ListNode *head;
    if (head1->val < head2->val)
    {
        head = head1;
        head1 = head1->next;
    }
    else
    {
        head = head2;
        head2 = head2->next;
    }
    ListNode *pre = head;
    while (head1 != NULL && head2 != NULL)
    {
        if (head1->val < head2->val)
        {
            pre->next = head1;
            head1 = head1->next;
        }
        else
        {
            pre->next = head2;
            head2 = head2->next;
        }
        pre = pre->next;
    }
    if (head1 != NULL)
    {
        pre->next = head1;
    }
    if (head2 != NULL)
    {
        pre->next = head2;
    }

    return head;
}

或

ListNode* merge(ListNode *head1, ListNode *head2)
{
    if (head1 == NULL)
    {
        return head2;
    }
    else if (head2 == NULL)
    {
        return head1;
    }
    ListNode *head;
    if (head1->val < head2->val)
    {
        head = head1;
        head1 = head1->next;
    }
    else
    {
        head = head2;
        head2 = head2->next;
    }
    head->next = merge(head1, head2);
    return head;
}

链表排序

ListNode* sort(ListNode *head)
{
    ListNode *p = head;
    int len = 0;
    while (p != NULL)
    {
        len++;
        p = p->next;
    }

    for (int i = 0; i < len - 1; i++)
    {
        p = head;
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (p->val > p->next->val)
            {
                swap(p->val, p->next->val);
            }
            p = p->next;
        }
    }
    return head;
}

树的子结构

bool subTreeHelp(TreeNode *root1, TreeNode *root2)
{
    if (root2 == NULL)
    {
        return true;
    }
    if (root1 == NULL)
    {
        return false;
    }
    if (root1->val != root2->val)
    {
        return false;
    }

    return subTreeHelp(root1->left, root2->left) &&
        subTreeHelp(root1->right, root2->right);
}

bool hasSubTree(TreeNode *root1, TreeNode *root2)
{
    bool res = false;
    if (root1 != NULL && root2 != NULL)
    {
        if (root1->val == root2->val)
        {
            res = subTreeHelp(root1, root2);
        }
        if (!res)
        {
            res = hasSubTree(root1->left, root2);
        }
        if (!res)
        {
            res = hasSubTree(root1->right, root2);
        }
    }

    return res;
}

二叉树的镜像

void mirror(TreeNode *root)
{
    if (root != NULL)
    {
        TreeNode *temp = root->left;
        root->left = root->right;
        root->right = temp;
        if (root->left != NULL)
        {
            mirror(root->left);
        }
        if (root->right != NULL)
        {
            mirror(root->right);
        }
    }
}