目录：
- 前言
- 一、相交链表
* - （一）题目分析
- （二）题目代码
- 二、环形链表 ①
* - （一）题目分析
- （二）题目代码
- 三、环形链表 ②
* - （一）解法1 — 数学分析，公式推导
– - （二）解法2 — 切断环，改变问题为相交链表
– - （三）解法3 — 改变链表，使得每个节点自环
– - 总结
前言
大家好，我是熊猫，今天我们来讲解几道有趣的链表题，希望大家可以在不断的打怪升级中提升自己的核心战斗力！
; 一、相交链表
给你两个单链表的头节点 headA 和 headB ，
请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
注意，函数返回结果后，链表必须 保持其原始结构 。
; （一）题目分析
我们先来看一下题目：
题目给了两个链表，这两个链表可能有相交部分，也可能没有，
如果有：就返回相交的第一个节点，
如果没有：就返回NULL.
需要注意的一点是：我们不能改变原链表。
1、最简单的方法：暴力破解 我们直接给它套上两层循环、依次遍历每个节点，
当两个节点都遍历到空时则表明没有相交节点，否则第一个想等的节点就是第一个相交的节点（相等指的是地址相等而非数值相等）。
不过显而易见，这种方法的时间复杂度为O(n^2)，空间复杂度为O(1)
这里我们可以先分别计算出两个链表的长度，计算它们的差值dif，
让长的链表先走dif步，之后两个链表就可以一起往前走，当两个节点相同时，我们就找到了第一个相交的节点，
当然，如果没有相交节点，两个链表最后都会指向空的。
动画演示：
相交链表–1
相交链表–2
（二）题目代码
代码如下：
typedef struct ListNode LN;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
int lenA = 0;
int lenB = 0;
LN* curA = headA;
LN* curB = headB;
while (curA->next)
{
lenA++;
curA = curA->next;
}
while (curB->next)
{
lenB++;
curB = curB->next;
}
if (curA != curB)
return NULL;
int dif = abs(lenA - lenB);
LN* longHead = headA;
LN* shotHead = headB;
if (lenA < lenB)
{
longHead = headB;
shotHead = headA;
}
while (dif--)
{
longHead = longHead->next;
}
while (longHead != shotHead)
{
longHead = longHead->next;
shotHead = shotHead->next;
}
return longHead;
}
提交实例：
二、环形链表 ①
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
; （一）题目分析
题目给了我们一个链表让我们判断链表中是否存在环，那么我们是否可以直接遍历一遍呢？
没有环就会遍历到NULL，那我们就可以直接返回FALSE，否则如果存在环的话就会走到重复的节点，那就返回TRUE不就好啦？
一开始肯定会有同学会这样想，但是实际上，如果不存在环的话我们很容易判断，可如果有环的话我们又怎么判断这个节点是已经走过的节点呢？我们只会在环中无限循序直至超出时间限制。我们需要换一种解题方式，这里我们只用一个指针时肯定无法判断一个节点是否已经走过的，那么我们是否可以再增加一个指针，两个指针走的速度不同，走的快的指针先入环，走的慢的指针后入环，
之后这个题目就变成了追及与相遇问题，两个指针都在环中走，走的快的肯定可以追上走的慢的，当它们相遇时就说明存在环，否则当走的快的遇到NULL时，就说明不存在环。
循环链表–1
循环链表–2
（二）题目代码
示例：
typedef struct ListNode LN;
bool hasCycle(LN* head) {
if (!head)
return false;
LN* fast = head;
LN* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return true;
}
return false;
}
提交实例：
上面我们写的fast速度为slow速度的两倍，其实也可以写成三倍，四倍，五倍等等，只要一个跑的快，一个跑的慢最后就都会相遇，不过跑过的圈数会有所不同。
三、环形链表 ②
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos
不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
（一）解法1 – 数学分析，公式推导
题目分析
在上一题我们能够确定一个链表中是否带有环，同时我们也看了相关的两个视频，
下面我们来分析一下两者的运动路程：
; 题目代码
示例：
typedef struct ListNode LN;
LN* hasCycle(LN* head) {
LN* fast = head;
LN* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return fast;
}
return NULL;
}
LN* detectCycle(LN* head)
{
if (!head)
return head;
LN* meet = hasCycle(head);
if (!meet)
return meet;
LN* cur =head;
while (meet != cur)
{
meet = meet->next;
cur = cur->next;
}
return meet;
}
提交实例：
（二）解法2 – 切断环，改变问题为相交链表
题目分析
在第二题中我们可以判断一个链表有没有带环，在第一题中我们可以找到一个两个相交链表的第一个相交节点，
说到这里我想大家已经知道我们下一步应该怎么做了吧！
我们在判断链表存在环之后可以将环从相遇点断开（新链表从相遇点开始），我们直接找相交链表的第一个相交节点即可。
视频解析：
切断循环链表
题目代码
示例：
typedef struct ListNode LN;
LN* hasCycle(LN* head) {
LN* fast = head;
LN* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return fast;
}
return NULL;
}
LN* getIntersectionNode(LN* headA, LN* headB) {
int lenA = 0;
int lenB = 0;
LN* curA = headA;
LN* curB = headB;
while (curA)
{
lenA++;
curA = curA->next;
}
while (curB)
{
lenB++;
curB = curB->next;
}
int dif = abs(lenA - lenB);
LN* longHead = headA;
LN* shotHead = headB;
if (lenA < lenB)
{
longHead = headB;
shotHead = headA;
}
while (dif--)
{
longHead = longHead->next;
}
while (longHead != shotHead)
{
longHead = longHead->next;
shotHead = shotHead->next;
}
return longHead;
}
LN* detectCycle(LN* head) {
if (!head)
return head;
LN* meet = hasCycle(head);
if (!meet)
return NULL;
LN* next = meet->next;
meet->next = NULL;
meet = next;
return getIntersectionNode(meet, head);
}
提交实例：
（三）解法3 – 改变链表，使得每个节点自环
题目分析
这里我们提供一种”错误的方法”：
遍历链表，每次都使相应的节点的next指针指向自己（自环），如果链表不带环就会走到NULL，如果链表本身就是带环的话我们就能够回到我们设置的自环节点，并且该节点就是入环的第一个节点。
（这里之所以说是错误的方法并不是说得不到正确的结果，只是这种方法对链表改动过大，无法通过LeetCode的检测）
视频解析：
切断循环链表2
题目代码
示例：
typedef struct ListNode LN;
LN* detectCycle(LN* head) {
if (!head)
return head;
LN* cur = head;
while (cur)
{
LN* next = cur->next;
if (cur == next)
return cur;
cur->next = cur;
cur = next;
}
return NULL;
}
运行实例：
总结
Original: https://blog.csdn.net/m0_66363962/article/details/127748509
Author: 熊猫馆主
Title: 【环形链表】
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/652599/
转载文章受原作者版权保护。转载请注明原作者出处！