题目 :
给出两个链表的头指针,比如h1,h2,判断这两个链表是否相交。
扩展:
(1) 如果链表可能有环呢?
(2) 如何求出两个相交链表的相交的第一个节点。
如果链表没有环
假设两个链表没有环,如果它们相交,那么它们的最后一个元素必定相同。
public boolean isConNLoop(ListNode h1, ListNode h2) { if (h1 == null || h2 == null) return false; ListNode n1 = h1; ListNode n2 = h2; while (n1.next != null) n1 = n1.next; while (n2.next != null) n2 = n2.next; if (n1 == n2) return true; return false; }
它们的交点为
public ListNode findPointNLoop(ListNode h1, ListNode h2) { if (h1 == null || h2 == null) return null; ListNode n1 = h1; ListNode n2 = h2; int len1 = 0; int len2 = 0; while (n1 != null) { n1 = n1.next; len1++; } while (n2 != null) { n2 = n2.next; len2++; } n1 = h1; n2 = h2; if (len1 < len2) { n1 = h2; n2 = h1; } for (int i = len1-len2; i > 0; i--) n1 = n1.next; while (n1 != null && n1 != n2) { n1 = n1.next; n2 = n2.next; } return n1; }
如果链表有环
如果链表有环且相交,那么这两个链表都是有环的。
找到第一个链表的环点,然后将环断开(当然不要忘记了保存它的下一个节点),然后再来遍历第二个链表,如果发现第二个链表从有环变成了无环,那么他们就是相交的嘛,否则就是不相交的了。
public boolean isConLoop(ListNode h1, ListNode h2) { ListNode temp = loopEntry(h1); ListNode org = temp.next; temp.next = null; if (isLoop(h2)) { temp.next = org; return false; } else { temp.next = org; return true; } } public ListNode loopEntry(ListNode head) { if (head == null) return null; ListNode slow = head; ListNode fast = slow.next; while (fast != null && fast.next != null && fast != slow) { slow = slow.next; fast = fast.next.next; } if (fast == slow) { fast = head; slow = slow.next; while (fast != slow) { slow = slow.next; fast = fast.next; } return slow; } return null; }
寻找环点的方法如下:
两个指针,一个走一步,一个走两步,在环中相遇位置为X。然后从头节点和X位置,分别一步一步的走,每次判断是否相遇,相遇点就是所求节点。
证明如下:假设头节点位置为A,环点为M,相遇节点为X,环长为Len。
因为快节点每次比慢节点快一步,慢节点进入环后快节点不用一圈就能赶上慢节点了。
慢节点走的路程 = AM + MX
快节点走的路程 = AM + MX + n * Len
=> 2*(AM + MX ) = AM + MX + n *Len
=> AM + MX = n*Len
=> AM = (n-1)*Len + XM,说明从A到M的距离与X到M的距离,模环长同余。因此分别从A和X走,必然相交于M节点。
当两个有环的链表相交时,有以下两种情况:
在这种情况下,两个链表的交点在环点之前,可以将环点切断,这样就变成了两个无环的链表求相交点。可使用以上方法。
另一种情况为:
在这种情况下,不存在所谓的相交点。
相关推荐
给出两个单向链表的头指针(如图3-8 所示),比如h1、h2,判断这两个链表是否 相交。这里为了简化问题,我们假设两个链表均不带环。
分析与解法 这样的一个问题,也许我们平时很少考虑。但在一个大的系统中,如果出现两个链表相 交的情况,而且释放了其中一个链表的...的两个链表,我们希望在释放一个链表之前知道是否有其他链表跟当前这个链表相交。
1.3.9 如何判断两个链表是否相交
主要介绍了C++将二叉树转为双向链表及判断两个链表是否相交的方法,文中还给出了求两个链表相交的第一个节点列的实现方法,需要的朋友可以参考下
可以看到如果把h1链表的尾节点的next指针指向h2链表的第一个节点,那么可以看到如果h1和h2相交,则h2变成了一个循环单链表,因此只需判断h2是否为循环链表
判断两个有环链表是否相交,相交则返回第一个相交节点,否则返回null 在考虑此问题时,根据前面几篇文章的解法,我们已经得到了各自链表的入环节点,分别为loop1和loop2 思路 以下是问题三的具体解决过程: 如果loop...
8. 找出链表的倒数第四个节点9. 找出链表的中间节点10. 判断单链表是否有环11. 判断两个链表是否相交, 如果相交, 计算交点12. 删除单链表中重复的元
算法大全-面试题-链表-栈-二叉树-数据结构.docx 一、单链表 ...判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
链表相关问题的完整代码,包括测试类和关键代码: **0、将链表翻转** **1、判断链表是否有环** **2、寻找环的入口点** **3、计算环的节点数** ...**6、判断两个无环链表是否相交** **7、寻找两个链表的相交的节点**
目录 1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 ...9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
判断两线段是否相交 8.判断线段与直线是否相交 9.点到线段最短距离 10.求两直线的交点 11.判断一个封闭图形是凹集还是凸集 12.Graham扫描法寻找凸包 数论: 1.x的二进制长度 2.返回x的二...
(1)、手写 C 语言版 strcpy 实现 (2)、最高效率判断两链表是否相交,及求出首次相交结点 (3)、一个只含有虚函数的类的 size 为多少 (4)、
判断两线段是否相交 8. 相交判断线段与直线是否 9.点到线段最短距离 10.求两直线的交点 11.判断一个封闭图形是 凹集还是凸集 12.Graham 扫描法寻找凸 包 数论: 1.x 的二进制长度 2.返回 x 的二进制表示 中从低到高...
//插入结点(连接两棵二叉树),这个结点(二叉树)和root不相交; //newTriNode可以是一个结点也可以是一棵二叉树 int InsertChildTriNode(TriTreeNode *newTriNode, TriTreeNode *root); //获取根结点 TriTreeNode *...
·动态规划的两个应用(第15.1节和第15.5节)。 ·利用随机化和线性规划技术的近似算法(第35.4节)。 ·为了使更多的算法可以更早地在书中出现,第1版中有关数学背景知识的三章内容从第一部分移到了附录中,即现在...
要求:能够对文件进行存储和读取。要求用一个结构记载学生属性,编写一个学生类以完成各种操作。...除学生成绩管理系统外,还包含判断线段是否与圆相交、时间计算器、按照要求设计类(根据输出设计类)等课程设计!
//rectInter用于计算两个矩形的相交区域 CRect rectInter; //point1和point2用于产生连接线最大矩形 CPoint point1; CPoint point2; drawrect.NormalizeRect (); drawrect.InflateRect (1,1); //遍历...
leetcode中国 2020年暑期编程练习 编程练习的题目 0、查漏补缺,将C语言基础语法必须全部学会...计算两个圆的公切线 求矩形的并的面积 求多边形面积 求多边形重心 求凸包 STL:了解STL,学习vector和list用法,请参考下