1.3：链表练习

一：递归找链表中的节点最大值

不难，但我觉得对理解递归的思想有用，就把自己写的代码贴上来了：

int max(Node first)
{
    if (first.next == NULL){ return first.a; }
    else{ return first.a > max(*(first.next)) ? first.a : max(*(first.next)); }
}

二：约瑟夫问题

N个身陷绝境的人一致同意通过以下方式减少生存人数，直到最后一个人留下来，从第一个人开始报数，报到M的人会被杀死，直到只剩一人，我贴一份以前的代码抛砖引玉（环形链表）：

class list
{
public:
    int val;
    list* next;
};

int main()
{
    while (1)
    {
        int num;
        int cnt;
        cin >> num >> cnt;

        //构造环形链表
        list* head = new list();
        head->val = 0;
        head->next = NULL;
        list* pre = head;
        for (int i = 1; i < num; ++i)
        {
            list* node = new list();
            node->val = i;
            pre->next = node;
            pre = pre->next;
        }
        pre->next = head;

        //打印出局顺序
        int copy = cnt-1;
        while (num--)
        {        
            while (copy--)
            {
                //找下一个不是负数的节点
                head = head->next;
                while (head->val < 0)
                {
                    head = head->next;
                }            
            }
            cout << head->val << endl;
            head->val = -1;
            copy = cnt;
        }
    }
    return 0;
}

三：栈与队列的互相转换

用两个栈实现队列

首先创建两个栈stack1，stack2。我们通过下图来直观理解如何实现队列的插入和删除操作：

插入元素：直接压入到stack1
弹出元素：
1. 当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以弹出
2. 如果stack2中为空时，我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端，经过弹出和压入之后就处于stack2的顶端了，又可以直接弹出

其实stack2中的出栈顺序和队列出队顺序一样的嘛，stack1作用是入队，负责中转一下

用两个队列实现栈

首先创建两个队列queue1，queue2。我们同样通过下图来直观理解如何实现栈的插入和删除操作：插入元素一直都是直接插入queue1
删除元素就要分三种情况了：

queue1和queue2都不为空（不太有这种情况）：queue1中的元素压入queue2中，queue1剩下一个元素弹出即可
queue1为空，queue2不为空，同样的queue2的元素压入queue1中，剩最后一个元素弹出
queue1不为空，queue2为空，同样的queue1的元素压入queue2中，剩最后一个元素弹出

大家可以看到，其实删除元素的三种情况也是类似的，基本都是把已有元素的队列中，除了最后一个元素外，其他全部压入另一个队列中，剩最后一个弹出，这样做的目的就是为了实现先入后出，因为队列不管怎么压入压出，它的元素顺序跟最开始的还是一样的，所以啊，很麻烦，我们为了操作一个元素，得移动所有的元素