有关算法的面试题收集

1. 对单链表排序，用代码实现【腾讯】

typedef struct Node {
    int data;
    struct Node *pNext;
} NODE, *PNODE;
//链表的长度
int length_list(PNODE pHead) {
    PNODE p = pHead->pNext;
    int len = 0;
    while (NULL != p) {
        ++len;
        p = p->pNext;
    }
    return len;
}
//对链表排序
void sort_list(PNODE pHead) {
    int i, j, t;
    int len = length_list(pHead);
    PNODE p, q;
    for (i = 0, p = pHead->pNext; i < len - 1; ++i, p = p->pNext) {
        for (j = i + 1, q = p->pNext; j < len; ++j, q = q->pNext) {
            if (p->data > q->data) {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
}

2. 快速找到未知长度的单链表的中间节点【腾讯】

• 普通方法：
  遍历一遍单链表以确定单链表的长度L, 然后再次从头结点出发循环L/2次找到单链表的中间节点。
  算法复杂度：O(L + L/2)=O(3L/2)。
• 利用快慢指针原理：
  设置两个指针search, mid都指向单链表的头结点。其中search的移动速度是mid的两倍。但*search指向末尾节点的时候，mid正好在中间了。
  代码实现(C语言)

typedef int ElemType;
typedef struct Node
{
    ElemType data; //数据域
    struct  Node *next; //指针域
} Node;
typedef struct Node *LinkList;
//快速找到未知长度单链表的中间节点 L:链表的头结点 *e返回的链表中间节点
bool GetMidNode(LinkList L, ElemType *e) {
    LinkList search, mid;
    mid = search = L;
    while (search->next != NULL) {
        if (search->next->next != NULL){
            search = search->next->next;
            mid = mid->next;
        } else {
            search = search->next;
        }
    }
    *e = mid->data;
    return true;
}

持续努力更新中......