`
steven-zhou
  • 浏览: 212388 次
  • 性别: 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;
}

分享到:
评论

相关推荐

    编程判断两个链表是否相交

    如果相交,可以通过计算两个链表的长度差来定位相交点。具体步骤如下: - 分别遍历两个链表,计算出它们各自的长度。 - 计算长度差 diff = |Length(h1) - Length(h2)|。 - 将较长链表的指针向前移动 diff 步,...

    编程判断两个链表是否相交.pdf

    但在一个大的系统中,如果出现两个链表相 交的情况,而且释放了其中一个链表的所有节点,那样就会造成信息的丢失,并且另一个与 之相交的链表也会受到影响,这是我们不希望看到的。在特殊的情况下,的确需要出现相交...

    实现两个链表类的链接

    本题的核心任务是实现两个链表类的链接,以便模拟加法运算,也就是将两个链表的元素相加。我们将详细探讨链表的结构、操作以及如何实现这个特定的加法功能。 首先,我们需要定义链表节点。每个链表节点通常包含两...

    50.两个链表的第一个公共节点1

    两个链表的第一个公共节点1"中,主要涉及的知识点是链表操作,特别是寻找两个链表的交点。这是一个常见的数据结构问题,旨在考察程序员对链表的理解以及解决问题的能力。以下是详细解释: 首先,链表是一种线性数据...

    两个链表求交集(链表基础练习)

    本题目的核心是利用链表的基本操作找到两个链表的交集,这是一个常见的算法问题,对于理解和掌握链表的操作具有很高的价值。 首先,我们需要了解链表的基本操作,包括创建链表、插入节点、删除节点和遍历链表。在...

    实现两个链表的合并

    (1)建立两个链表A和B 链表元素个数分别为m和n个 (2)假设元素分别为 x1 x2 …xm 和 y1 y2 …yn 把它们合并成一个线性表C 使得: 当m> n时 C x1 y1 x2 y2 …xn yn … xm 当n>m时 C y1 x1 y2 x2 …ym xm ...

    PTA 两个有序链表序列的合并

    这个题目“PTA 两个有序链表序列的合并”主要涉及到链表的操作和合并策略,这对于理解和掌握链表操作有极大的帮助。下面我们将深入探讨这个主题。 链表是一种线性数据结构,它由一系列节点组成,每个节点包含数据和...

    两个链表的合并

    "两个链表的合并"这个话题是关于如何将两个已经排序的链表合并成一个新的有序链表。这个问题经常在面试中出现,因为它能够考察程序员对链表操作的理解以及问题解决的能力。下面我们将详细讨论这个知识点。 首先,...

    判断链表是否相交的几种算法1

    该方法通过将h1链表的尾节点的next指针指向h2链表的头节点,如果两个链表相交,此时h2会形成一个循环链表。接下来只需判断h2是否为循环链表,可以使用Floyd判断环算法或龟兔赛跑算法。这种方法的时间复杂度同样是O...

    数据结构_两个链表的合并一元多项式相加

    ### 数据结构:两个链表的合并与一元多项式相加 #### 1. 链表基础概念 链表是一种常见的线性数据结构,它由一系列节点组成,每个节点包含数据元素和一个指向下一个节点的引用(指针)。在本场景中,链表用于表示...

    连接两个链表(使用链表创建).txt

    连接两个链表涉及到遍历两个链表并根据一定规则合并它们。在给定的代码中,连接过程实际上是对两个链表进行排序合并,即按照节点数据的大小顺序依次连接节点。这一过程可以视为一种特殊的排序算法,类似于归并排序的...

    链表归并的操作,将两个链表合并成一个链表

    当我们面临两个已排序的链表需要合并成一个有序链表时,链表归并操作显得尤为重要。这种操作通常出现在诸如合并排序等算法中,其目的是有效地整合两个已经排序的链表,保持合并后的链表依然有序。 在链表归并的过程...

    1.3.9 如何判断两个链表是否相交.md

    1.3.9 如何判断两个链表是否相交

    两个有序链表序列的合并_C语言_

    在编程领域,特别是数据结构和算法中,"两个有序链表序列的合并"是一个常见的问题。这个问题要求我们合并两个已排序的链表,使得合并后的链表仍然保持非降序排列。在这里,我们主要讨论如何使用C语言来解决这个问题...

    将两个递增的链表合并为一个非递减的链表

    本题目要求实现的功能是:输入两个递增的链表,然后通过程序对这两个链表进行排序(虽然在实际应用中,递增的链表已经有序,这里排序步骤是为了确保链表有序),接着按照递增顺序合并这两个链表,最终输出合并后的...

    实现两个链表的合并(数据结构课程设计c语言版)

    实现两个链表的合并(数据结构课程设计c语言版)

    将两个有序链表合并一个链表

    将两个有序的链表合并为一个有序链表,链表的大小是可变的

    链表实现两个多项式的相加

    本主题关注的是如何使用链表来实现两个多项式的相加。在这个过程中,我们将深入理解链表的特性,并探讨如何利用这些特性来处理数学中的多项式运算。 首先,让我们了解一下链表的基本概念。链表是一种线性数据结构,...

    何将两个有序链表并为一个有序链表

    何将两个有序链表并为一个有序链表。

Global site tag (gtag.js) - Google Analytics