开篇记录面试第17天

说真的，早上收到了一个准offer的电话，感觉心态一下子就轻松了很多。当然，我知道那并不是我本意，我要做的还有很多，毕竟以我的能力，再不去个大厂学习学习，后面肯定更没啥出路了。不过条件合适的话，小厂也可以，嘿嘿，我就是这么随意。

正题。今天面试了最右，就问了两个问题，基本没答上来，就凉了。

1. 实现带头结点的单链表的快速排序。
   2.给定一个乱序的数组，多次给出一个起始点的下标s和结束点e，要求快速给出s和e之间最小的数。

思考：

1. 快排需要前后两个指针同时移动，那如果是单链表，不能前后移动的话怎么办呢，这时候就可以用p和q两个指针，同时朝一个方向移动。https://blog.csdn.net/yc_wj/article/details/65935262我是参照的这篇博客里的方法，当然这个作者把配图里的说明写错了，导致我理解了半天，其实原理就很简单，就是说，两个指针同时移动，i是前面那个，j是后面那个，如果j的值小于选定的key，就让i向后移动一个，并且把j和i所指的值交换。当j走到末尾的时候结束一次迭代，这时候把key和当前i指向的值交换。返回这个i的下标，然后进行递归调用。
   代码如下：(代码里struct的定义我不是很懂，为什么加了个Node的函数)

struct Node 
{
    int key;
    Node* next;
    Node(int nKey, Node* pNext)
        : key(nKey)
        , next(pNext)
    {}
};
 
 
Node* GetPartion(Node* pBegin, Node* pEnd)
{
    int key = pBegin->key;
    Node* p = pBegin;
    Node* q = p->next;
 
    while(q != pEnd)
    {
        if(q->key < key)
        {
            p = p->next;
            swap(p->key,q->key);
        }
 
        q = q->next;
    }
    swap(p->key,pBegin->key);
    return p;
}
 
void QuickSort(Node* pBeign, Node* pEnd)
{
    if(pBeign != pEnd)
    {
        Node* partion = GetPartion(pBeign,pEnd);
        QuickSort(pBeign,partion);
        QuickSort(partion->next,pEnd);
    }
}

2.第二题看起来是个动态数组的问题，明天好好找找思路吧。今晚太晚了，就不搞了。