摘要：还是链表算法题目描述给出两个无环单链表判断和是否相交。所以可以得出另外一种解法，先遍历链表，记住尾节点，然后遍历链表，比较两个链表的尾节点，如果相同则相交，不同则不相交。想法还是奇妙的。算法写起来不难，难的是想到这个。
还是链表算法
题目描述：给出两个无环单链表
A: a1 → a2
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
判断 A 和 B 是否相交。
除了转化为环的问题，还可以利用“如果两个链表相交于某一节点，那么之后的节点都是共有的”这个特点，如果两个链表相交，那么最后一个节点一定是共有的。所以可以得出另外一种解法，先遍历 A 链表，记住尾节点，然后遍历 B 链表，比较两个链表的尾节点，如果相同则相交，不同则不相交。时间复杂度为 O(Length(A) + Length(B))，空间复杂度为 O(1)，思路比解法 2 更简单。想法还是奇妙的。算法写起来不难，难的是想到这个。
function hasSharedNode(head1, head2){
if(head1 == null||head2 == null) return false;
var lastNode1 = head1;
while(lastNode1.next != null){
lastNode1 = lastNode1.next;
}
var lastNode2 = head2;
while(lastNode2.next != null){
lastNode2 = lastNode2.next;
}
if(lastNode1 == lastNode2){
return true;
}
else {
return false;
}
}
两个链表相交扩展：判断两个有环单链表是否相交
题目描述：上面的问题是针对无环链表的，如果是链表有环呢？
分析：如果两个有环单链表相交，那么它们一定共有一个环。因此可以先用之前快慢指针的方式找到两个链表中位于环内的两个节点，如果相交的话，两个节点在一个环内，那么移动其中一个节点，在一次循环内肯定可以与另外一个节点相遇。
有环单链表到底是咋样的，就是我们前面说的小b型的结构吧。尾节点的next指向前面的某个节点。如果交点不是在环上，那么肯定是共享一段直线加上一个环。
如果交点是在环上，那么就是共享环，直线阶段是各自独立的。所以结果就是共有一个环。需要用到上次找环入口的那个function。为啥不能用无环链表的算法呢？因为没法判断尾节点。其实也算是用到了，其实环入口就算是尾节点吧。
function findLoopPort(head){
if(head==null||head.next==null) return null;
var fastNode = head;
var normalNode = head;
var hasCircle = false;
while(fastNode != null&&fastNode.next != null){
fastNode = fastNode.next.next;
normalNode = normalNode.next;
if(normalNode == fastNode) {
hasCircle = true;
break;
}
}
if(!hasCircle) return null;//原本想return false，后来发现还是null好。
var fastNode = head;
while(fastNode != normalNode){
fastNode = fastNode.next;
normalNode = normalNode.next;
}
return fastNode;
}
function hasSharedNodeWithLoop(head1, head2){
var loopPort1 = findLoopPort(head1); //head1 head2的null之类的已经在findLoopPort里面判断了。
var loopPort2 = findLoopPort(head2);
if(loopPort1 == null || loopPort2 == null){ //无环，则不满足条件，即使无环单链表相交，也返回false
return false;
}
var startNode = loopPort1;
while(loopPort1.next != startNode){ //保证只在环内转一圈
if(loopPort1 == loopPort2)
return true;
loopPort1 = loopPort1.next;
}
return false; //转完一圈没发现共同的节点，则没相交点。
}
两个链表相交扩展：求两个无环单链表的第一个相交点
LeetCode 160. Intersection of Two Linked Lists
题目描述：找到两个无环单链表第一个相交点，如果不相交返回空，要求在线性时间复杂度和常量空间复杂度内完成。我的想法是如果求得最后一个尾节点，然后让尾节点的next指向其中的一个的头，那么肯定就构成了一个有环单链表。然后求得环的入口就是第一个相交点。主要是感觉一步一步的，好像都在复用前面的东西。所以就想到了这个。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/90233.html
摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...
摘要：算法系列单源最短路径算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。 Javascript算法系列 - 单源最短路径 - Dijkstra算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有...
摘要：因为是在已经分组排序过的基础上进行插入排序，所以效率高。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。形成左右两个分区，再递归按之前的步骤排序。 算法复杂度 不是科班生的我，第一次看见时间复杂度之类的名词表示很懵逼，所以就找了网上的资料补习了下： 时间复杂度：是指执行算法所需要的计算工作量 空间复杂度：是指算法在计算机内执行时所需存储空间的度量 排序算法稳定性： 假定在待...
摘要：回顾选择排序，插入排序，冒泡排序，快速排序，希尔排序，归并排序，堆排序以及如何计算时间复杂度学习文章同学的描述数据结构等同学的十大经典算法本文代码也上传到了排序算法回顾。但希尔排序是非稳定排序算法。 回顾选择排序，插入排序，冒泡排序，快速排序，希尔排序，归并排序，堆排序以及如何计算时间复杂度学习文章：hahda同学的javascript描述数据结构、hustcc等同学的十大经典算法 ...
摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法为王。想学好前端，先练好内功，内功不行，就...
摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法为王。 想学好前端，先练好内功，...
阅读 3468·2021-09-02 09:53
阅读 1790·2021-08-26 14:13
阅读 2749·2019-08-30 15:44
阅读 1313·2019-08-30 14:03
阅读 1961·2019-08-26 13:42
阅读 3013·2019-08-26 12:21
阅读 1301·2019-08-26 11:54
阅读 1899·2019-08-26 10:46
