百度面试

1、快排，链表中间节点

求链表的倒数第 k 个节点」很相似。可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第3题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。

这么理解：slow节点：走了X个节点—L/2; fast节点：走了2x个几点—–L长度。共X步。

引申：如何找出链表的前第1/3个链表长度的节点。就是:slow: x步—L/3节点。fast: L节点。所以，fast每次走三步。

//求链表的中间节点
Node* theMiddleNode(Node *head)
{
    if(head == NULL)
        return NULL;
    Node *slow,*fast;
    slow = fast = head;      //如果要求在链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件
    //while(fast && fast->next != NULL && fast->next->next != NULL)  
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

2、数据库内连接，外连接

3、用qq号查询昵称字段怎么优化

字符串压缩、哈希表存储和查找

4、用宏定义定义返回最大值的函数

#define max(a,b)  (((a)>(b))?:((a):(b))

5、二分查找，手写。

6、前序遍历二叉树，手写。

7、给了一棵树，写出前中后序遍历。

8、了解哪些常用设计模式?

1、创建对象模式：

单例模式：单例模式也称为单件模式、单子模式，可能是使用最广泛的设计模式。其意图是保证一个类仅有一个实例，并提供一个访问它的全局访问点，该实例被所有程序模块共享。比如一个鼠标、一个窗口管理器、一个键盘。

简单工厂模式：一个工厂类返回不同的产品类

工厂方法模式：多个工厂类，不同工厂类返回不同的产品类

抽象工厂模式：根据不同的产品类系，抽象不同的工厂类来生产

2、结构模式：

适配器模式：将一个类的接口转换成客户希望的另外一个接口。适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

3、行为型模式

策略模式：定义一系列的算法,把它们一个个封装起来, 并且使它们可相互替换。

9、import和include区别

10、给千万量级的珠子，共上百种颜色，围成一个圈，求连续的包含所有颜色的最短子串的长度，并分析时间复杂度

两个指针，开始的时候都指向某一个位置，移动前一个指针，直到两个指针直接包含了所有颜色的珠子。 此时记下len。 然后向前移动后面的指针，再调整最前面的指针，直到重新满足两个指针间包含了所有的颜色，比较此时的len和之前的len，取最小值。 如此移动，直到后面的指针回到起始位置。 时间复杂度是O（N），空间复杂度是O(1)