`

如何判断两个单向链表是否有相交,并找出交点

阅读更多

 

题比较简单,单向链表有交点意思就是交点后的节点都是一样的了

 

NODE* FindNode(NODE* pHead1, NODE* pHead2)
{
     NODE* p1 = pHead1;
     NODE* p2 = pHead2;
    int i = 1, j = 1, k = 0, f = 0;

    if(pHead1 == NULL || pHead2 == NULL)
    {
        return NULL;
    }

    while(p1->next != NULL)
    {
         p1 = p1->next;
         i++;
    }

    while(p2->next != NULL)
    {
         p2 = p2->next;
         j++;
    }

    if(p1 != p2)
    {
        return NULL;
    }
    else
    {
         p1 = pHead1;                // 1
         p2 = pHead2;

         f = fabs(i-j) //求绝对值的函数
        if(i > j)                    // 2
        {
            for(k=0; k<f; k++)
            {
                 p1 = p1->next;
            }
            while(p1 != p2)
            {
                 p1 = p1->next;
                 p2 = p2->next;
            }
            return p1;
        }
        else
        {
            for(k=0; k<f; k++)
            {
                 p2 = p2->next;
            }
            while(p1 != p2)
            {
                 p1 = p1->next;
                 p2 = p2->next;
            }
            return p1;
        }
    }
}

1,在第一次遍历完链表后,进行第二次遍历,需要把指针再次初始化;看见网上一些人给的例子没有再次初始化显然是错误的;再调用NULL的next不死才怪!

2,小优化。循环和判断,把判断放在外面;如果把i和j大小判断放在里面的话就意味着循环多少次,判断就执行多少次;当然这样做的唯一不足就是代码多了点;还有for循环之前的对f的赋值,有的为了简便直接放在for语句里面,不过同样道理,放在for循环里面,就执行了n次的fabs;拿出来赋值,只赋值一次就OK。

分享到:
评论

相关推荐

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

    本篇文章将详细探讨如何判断两个单向链表是否相交的问题,以及相应的解决方案。 #### 问题背景 在实际应用中,尤其是在大型系统开发过程中,可能会遇到两个链表相交的情况。例如,当两个链表共享部分节点时,如果不...

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

    题目要求编写一个程序,用于判断两个单向链表是否相交。这里假设两个链表均不包含环。为了简化问题,我们将重点放在如何有效地确定两个链表是否相交上,并探索不同的解决方案。 #### 解法一:直观的想法 最直观的...

    [剑指-Offer] 52. 两个链表的第一个公共节点(思维、快慢指针、巧妙解法)

    题目的具体要求是,给定两个单向链表,找出它们的第一个公共节点。这个问题的难度在于,两个链表可能有不同的长度,并且在相交之前可能各自走过不同的路径。这就意味着,直接遍历其中一条链表寻找交点并不总是可行的...

    js-leetcode题解之160-intersection-of-two-linked-lists.js

    解决这类问题的一种常见思路是通过哈希表来存储已经访问过的节点,然后遍历另一个链表,查找哈希表中是否已经存在该节点,这样可以很快判断出两个链表的交点。但这种方法会增加空间复杂度。 一种更为巧妙的解法是,...

    java二叉树算法源码-DataStructure:常用数据结构及其算法的Java实现,包括但不仅限于链表、栈,队列,树,堆,图等经典数据结构

    单向链表的数据结构及其相关算法:单向链表结构包含两个要素,即头结点head和链表大小size,具体操作包括: 链表的增删 链表是否为空 链表的大小 链表的打印输出 删除链表重复节点 链表倒数第K个元素 链表的反转 ...

    深信服2008校园招聘笔试题

    8. **链表相交**:判断两个单向链表是否有交点并找到交点,可以采用双指针法,一个从头开始遍历,另一个从交点开始遍历,直到两个指针相遇。 9. **球和箱子问题**:这是一个组合优化问题,可能需要使用动态规划或...

    觅职渣记-互联网技术类笔试面试总结

    给定两个单向链表,判断它们是否相交,并找到第一个公共节点。 **4. 链表内环的存在问题** 判断链表中是否存在环,常用的方法是快慢指针法。 **5. 链表逆置反向存储** 链表逆置是将链表的节点顺序反转的过程。 ...

Global site tag (gtag.js) - Google Analytics