笔试面试--数据结构

==================================链表==================================

1. 找一个链表中倒数第k个结点（假设原链表肯定有多余k个结点）

假设整个链表有x个结点，用两个指针即可找到倒数第k个，示意图如下：

先用一个指针a遍历到第k个 ；然后a、b指针同时开始往后，直到指针a结束，则b在这段时间里走过了x-k个结点，也就是倒数第k个结点

typedef struct {
    int data;
    Node *next;
}Node;

Node *findKthToTail(Node *head,int k)
{
    //假设链表不为空，且有多于k个结点
    Node *fast = head;
    Node *slow = head;
    for(int i=0;i<k;i++) {
        if(fast == NULL) {
            return NULL;
        }
        fast = fast->next;
    }
    while(fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

2. 单链表排序

3. 两个单链表求交、并、差

4. 单链表反转

Node是结点结构体类型:有数据域elemType data和指针域Node *next
第一个结点就是有效结点
Node *head = initSingleList();
//.....加入了很多新元素进去
reverseSingleList(&head); //或head = reverseSingleList(&head);

Node *reverseSingleList(Node **head)
{
    if(NULL == *head || NULL == (*head)->next) {
        return *head;
    }
    Node *a = *head;
    Node *b = a->next;
    Node *c = NULL;
    (*head)->next = NULL;
    while(NULL != b) {
        c = b->next;
        b->next = a;
        a = b;
        b = c;
    }
    *head = a;
    return a;
}

==================================二叉树==================================

1. 结点数量相关问题

（1）不同度结点的关系

（2）计算结点总数

https://www.cnblogs.com/taoXiang/p/12324454.html

（3）树深度

https://www.cnblogs.com/taoXiang/p/12324454.html

2. 二叉树形状推导

（1）已知前序遍历和中序遍历

前序：ABDHIEJKCFLMGNO

中序：HDIBJEKALFMCNGO

还原：

　　分块，区分哪一块是左边的、哪一块是右边的：

　　　　【A B DHI EJK C FLM GNO】

　　　　【HDI B JEK A LFM C NGO】

　　①根据前序，A是最上面的结点，根据中序，则【HDI B JEK】为A左侧结点，【LFM C NGO】为A右侧结点

 　　　　②分析A左侧这部分，右侧类似

　　分析【B DHI EJK】【HDI B JEK】，B是根，【DHI】为B左侧结点，【JEK】为B右侧结点

　　分析【C FLM GNO】【LFM C NGO】，C是根，【FLM】为C左侧，【GNO】为C的右侧结点

　　③

　　　　分析【DHI】【HDI】，D是根，H为D左侧点，I为D右侧点

　　　　分析【EJK】【JEK】，E为根，J为E左侧点，K为E右侧点

　　　　分析【FLM】【LFM】，F为根，L为F左侧点，M为F右侧点

　　　　分析【GNO】【NGO】，G为根，N为G左侧点，O为G右侧点

（2）已知后序遍历和中序遍历

后序：HIDJKEBLMFNOGCA

中序：HDIBJEKALFMCNGO

（3）已知后序遍历和前序遍历

无法推断