【数据结构】——链表OJ(下)

前面我们已经刷了几道单链表的题目，下面我们继续看几道题目。

一、相交链表

这道题题目的要求是很好理解的，就是现在我们有两个链表，然后我们就相办法进行判断，这两个链表是否是相交的，那么链表的相交其实就是有没有共同的节点，所以，我们很快可以想到的是，我们去遍历两个链表，然后看其节点是否会有相同的部分。但是我们拿上面题目的例子会发现这样是行不通的，这是因为我们的链表的长度不一样，所以到相交点的距离是不一样的，那么我们遍历的话，是没办法同一个循环到这个节点的。那么我们是否可以先求出两个链表的长度，然后我们求其长度的差，然后让较长的链表先走长度差，然后再一起进行遍历判断节点是否相同呢？

下面我们试试这个方法：

 

可以看到这种方法是可行的，那么我们有的朋友可能会有点疑问，题目是要求返回的是这个开始相交的节点，那么我们长的链表先进行遍历是否会先进入这个相交的节点呢，其实是不会的，这就要提到我们链表相交的几种情况了：

 

链表相交就基本上是上面的几种情况了， 有的朋友可能会想到我们的X型的相交情况，但是这种相交在链表中是不会存在的，这是因为我们的单链表一旦相交，那么其后面的下一个节点都是一样的了，不会出现这种情况。然后就是上面提到的，先走的链表会不会出现先到相交节点的情况，这其实也是不会的，这是因为我们通过上面的图可以发现，其实我们两个链表的相交节点到链表的尾节点的距离是一样的了，那么我们先走几步也是不会到这个相交节点的。如果先到，那么相交节点到尾节点的这个距离相等的结论也就不成立了。

那么我们发现如果两个链表相交的话，那么我们的尾节点是一定会相等的，但是我们这道题的话要返回开始相交的节点，所以这样不行的。但是如果是判断是否相交就可以这样了。   

二、环形链表（1）

这道题题目的要求就是，其有一个链表，然后这个链表中，可能会形成环的结构，那么我们可以进行遍历链表，创建两个指针进行遍历，判断其节点的是否相等，如果相等，那么就是环，但是我们这两个指针该如何进行创建呢？我们要是都再头节点开始，那么我们就会导致我们一开始这两个指针就是一样的，所以这个是行不通的，其实我们还是可以用到我们前面学习到的快慢指针，一个指针一次走两步，一个指针一次走一步，然后快的指针就会先进环，然后慢的指针再进环，然后这两个指针就会在环内进行追逐，但是我们是否可以保证其在环内一定可以碰上呢，一个走步，一个走一步的话，我们会发现其之间相差的距离会缩小一个节点，那么其最终肯定是可以碰上的。那么如果是一个走三步，一个走一步呢？

我们来分析一下，比如，当前我们的两个指针，相差的距离是N，那么我们每次遍历，那么两个指针的距离就会变成N-2，然后继续循环，那么其情况就有两种，一种就是N一开始是偶数，那么其一直会直接走到0，那么此时两个指针就会相遇了，那么如果N是奇数呢，那么其最后两个指针的距离是变成N-2->N-4->N-6.......->5->3->1->N-1，那么此时就会进入到第二圈的追逐，那么我们会发现第二圈开始追逐，此时两个指针之间要追逐的距离变成了偶数，所以我们可以发现，其不管快慢指针之间相差多少，其最终都还是会相遇的。

那么我们循环的条件是啥呢？我们直接设置为快指针即可，这是因为快指针走的快，如果这是个非环形链表，那么其快指针会很快走到空，那么就可以结束循环，如果是环形链表，那么其就会在圈内追逐，直到相遇，不过，要注意的是，我们的快指针在遇到非环形指针时，如果链表是偶数个节点，那么我们如果直接使用快指针，那么其在刚刚好到达尾节点，其要是往下走两步，那么就会造成对空指针进行解引用了。所以我们循环的条件设置为快指针和快指针的下一个指针。

代码如下：

 

 三、环形链表（2）

这道题就是上面第一个环形链表的升级版了，这里不单要判断链表是否为环，然后还要返回第一个入环的节点，例如上面就要找到2这个节点。

这里我们就直接用一个结论就行，就是环形链表中。我们的快慢指针相遇的点，和头节点到入环的节点的距离是一样的。那么我们可以先让快慢指针先相遇，然后再创建一个指针从头节点开始往后遍历，慢指针也开始遍历，然后慢指针和这个保存着头节点的指针相遇的节点就是入环的节点。

如下：

 

四、随机链表的复制 

 这道题会发现和我们上面的链表是有点不一样的吗，这些链表会比我们前面学习的链表多了一个节点指针，这个多的指针是随机指向的，当前题目是要我们将原链表进行拷贝，形成一个新的链表，然后其除了地址不同，其他的都是一样的。

那么我们如何进行拷贝呢？

如果是单单的拷贝普通的链表我们还是很好搞定，不过我们还是要向操作系统进行节点的申请，那么我们要写一个申请节点的操作。

我们直接将思路吧，我们这个题目主要是对于拷贝后的rondom如何进行寻找。我们可以先拷贝这个节点，然后将这个拷贝的节点插到原链表中原节点的后面，然后再对rondom进行处理，然后再将这个拷贝的链表和原链表进行断开。

下面我们来通过代码实现吧：

 

 

谢谢大家的阅读，给个三连吧。