一.线性表

1.两个等长的升序数组，求两个数组所有元素的中位数

//分别求两个升序序列A，B的中位数分别为ma，mb.
//当ma == mb 即为中位数
//当ma > mb 舍弃A中大的部分和B中小的部分
int ddd(int a[], int b[], int n)
{
    int la = 0, lb = 0, ra = n - 1, rb = n - 1, ma, mb;
    int k = 0;
    while(la != ra || lb != rb)
    {
        if(k == 5) break;
        k ++;
        ma = (la + ra) >> 1;
        mb = (lb + rb) >> 1;
        if(a[ma] == b[mb]) return a[ma];
        if(a[ma] < b[mb])
        {
            int t = (la + lb) % 2; // 偶数为1奇数为0
            la = ma + t;
            rb = mb;

        }
        else
        {
            int t = (la + lb) % 2; // 偶数为1奇数为0
            lb = mb + t;
            ra = ma;
        }
    }
    return a[ra] < b[rb] ? b[rb] : a[ra];
}

2.链表判环，并找到入口点

①是否有环
快慢指针，快的走两步，慢的走一步，相遇则有环。

②找入口点
有3个点：头节点，入口点，相遇点（快慢指针）。
头节点到入口点距离为a，入口点到相遇点距离为x，环长为r

slow进入环，第一圈没走完就会被追上。则slow走的距离为a + x.
fast比slow多走的为n倍环长即a + x + n * r.

距离：fast = slow * 2，得 a = n * r - x.
也就是说头节点到入口点的距离和相遇点到入口点的距离相同（在模环长的情况下）
让指针从头节点和相遇点同时出发，再相遇的点为入口点。

LNode *Loop(LNode *head) //链表判环
{
    LNode *fast = head, *slow = head; //快慢指针
    while(fast->next)
    {
        if(!fast->next) return NULL;
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) break;
    }
    if(fast != slow) return NULL; //无环

    LNode *p = head;
    while(p != slow)
    {
        p = p->next;
        slow = slow->next;
    }
    return p;
}