2015-941

2015-941

1.判断两个单链表是否相交

• 两个单链表的头指针分别为head1和head2
• 如果相交则返回第一个交点
• 要求算法的时间复杂度为$O(length1+length2)$

（1）算法思想

• 先创建一个子函数求出链表长度
• 主函数：
• 因为两个链表如果相交，则两个链表中从某一结点开始往后一定全一样
• 所以长链表比锻炼表前面多出的部分不可能存在交点
• 利用链表的长度差值n，长链表从第n+1个结点，短链表从第一个结点开始，同时开始遍历

int len(LinkList L){
    int i = 0;
    LNode *p = L;
    while(p != NULL){
        i++;
        p = p -> next;
    }
    return i;
}
LNode Search(LinkList head1,LinkList head2){
    int length1 = len(head1);
    int length2 = len(head2);
    int n;
    LNode *q = head1;
    LNode *s = head2;
    if(length1 > length2){
        n = length1 - length2;
        for(int j = 0; j < n; j++){
            q = q -> next;
        }
    }
    if(length1 < length2){
        n = length2 - length1;
        for(int j = 0; j < n; j++){
            s = s -> next;
        }
    }
    while(q != NULL && q -> data != s -> data){
        q = q -> next;
        s = s -> next;
    }
    return q;
}

2.二叉树各层独生叶结点的数目

• 独生叶结点（既是叶结点又无兄弟结点）
• root指向二叉树根结点的指针
• 输出各层独生叶结点的数目

int shumu(BiTree root){
    BiTree p = root;
    int front = -1, rear = -1;
    int level = 1;//层数
    int last = 0;
    int Queue[];
    if(p = NULL){
        return 0;
    }
    Queue[++rear] = p ;
    while(front != rear){
        int num = 0;
        p = Queue[++front];
        if(p -> lchild && p -> rchild){   
            Queue[++rear] = p -> lchild;
            Queue[++rear] = p -> rchild;
            if(front == last){
                level++;
                last = rear;
                printf("%d",level);
                printf("%d",num);
            }
        }
        if(p -> lchild && p -> rchild = NULL){
            Queue[++rear] = p -> lchild;
            num = num + 1;
            if(front == last){
                level++;
                last = rear;
            }
        }
        if(p -> rchild && p -> lchild = NULL){
            Queue[++rear] = p -> rchild;
            num = num + 1;
            if(front == last){
                level++;
                last = rear;
                printf("%d",level);
                printf("%d",num);
            }
        }
    }
}