`
steven-zhou
  • 浏览: 207888 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

判断两个链表有无交点,如果有请给出交点

阅读更多
/*
 * if list_a and list_b has cross point return the addrss of cross-point.
 * else return NULL
 */
static List *has_cross(List *list_a, List *list_b)
{
    List    *pa;
    List    *pb;
    int     len_a, len_b;
    int     i;

    len_a = len_b = 0;

    pa = list_a; /* 遍历链表a,并记录下此链表的长度 */
    while (pa->next != NULL) {
        pa = pa->next;
        len_a++;
    }

    pb = list_b; /* 遍历链表b,并记录下链表b的长度 */
    while (pb->next != NULL) {
        pb = pb->next;
        len_b++;
    }

    if (pa != pb) /* 如果指针pa,pb最后不相等,则两链表没有焦点 */
        return NULL;

    /* 较长的链表先向后调整到第N个元素(N = max(len_a, len_b) - min(len_a, len_b))
然后两链表同步向后调整,同时比较地址是否相等,如果相等则为首焦点。*/
    pa = list_a;
    pb = list_b;
    if (len_a > len_b) {
        for (i = len_a - len_b; i; i--)
            pa = pa->next;
    } else {
        for (i = len_b - len_a; i; i--)
            pb = pb->next;
    }

    while (pa != pb) {
        pa = pa->next;
        pb = pb->next;
    }
    return pa;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics