环形链表相关的练习
目录
一、相交链表
二、环形链表
三、环形链表 ||
一、相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
代码实现：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{// 1. 分别找到两个单链表的尾结点，并计算它们的长度struct ListNode *tailA = headA, *tailB = headB;int lenA = 1, lenB = 1;while (tailA->next != NULL){++lenA;tailA = tailA->next;}while (tailB->next != NULL){++lenB;tailB = tailB->next;}if (tailA != tailB) // 如果两个链表不相交，则尾结点的地址不同{return NULL;}// 2. 让指向长链表的指针先走差距步int gap = abs(lenA - lenB);struct ListNode *longCur = headA, *shortCur = headB;if (lenA < lenB){longCur = headB;shortCur = headA;}for (int i = 0; i < gap; ++i){longCur = longCur->next;}// 3. 让 longCur 和 shortCur 同时向后走，直到找到相同地址的结点while (longCur != shortCur){longCur = longCur->next;shortCur = shortCur->next;}return longCur;
}
二、环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
-
链表中节点的数目范围是
[0, 10^4] -
-105 <= Node.val <= 105 -
pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
代码实现一：
bool hasCycle(struct ListNode *head)
{struct ListNode* addr[10000] = { 0 }; // addr 是保存每个结点地址的指针数组int pos = 0; // pos 始终是第一个未存放结点地址的数组下标struct ListNode* cur = head;while (cur != NULL){addr[pos++] = cur;// 检查 cur->next 是否指向之前的结点或自己for (int i = 0; i < pos; ++i) {if (addr[i] == cur->next){return true;}}cur = cur->next;}return false;
}代码实现二（快慢双指针）：
bool hasCycle(struct ListNode *head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next) // 如果链表不带环，则快指针先走到空或尾{slow = slow->next;fast = fast->next->next;if (slow == fast){return true;}}return false;
}问题（前提是链表带环）：
-
快慢指针从相同的起始位置出发，慢指针 slow 每次走一步，快指针 fast 每次走两步，请问这两个指针为什么一定会再次相遇？
设当 slow 走到入环的第一个结点时，fast 距 slow y 步（0 <= y <= C，C 表示环的长度），然后 slow 走 x 步，fast 走 2x 步后，两个指针再次相遇，则有：2x - x = y，即 x = y。
y == 0，即当 slow 走到入环的第一个结点时，就和 fast 再次相遇了；y == C，即入环的第一个结点就是头结点，如示例 2。
-
快慢指针从相同的起始位置出发，慢指针 slow 每次走一步，快指针 fast 每次走 n 步（n >= 3），请问这两个指针也一定会再次相遇吗？
n * x - x = y，即 (n - 1)x = y ==> x = y / (n - 1)。
例如：
三、环形链表 ||
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
-
链表中节点的数目范围在范围
[0, 10^4]内 -
-105 <= Node.val <= 105 -
pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
代码实现一：
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* addr[10000] = { 0 };int pos = 0;struct ListNode* cur = head;while (cur != NULL){addr[pos++] = cur;for (int i = 0; i < pos; ++i){if (addr[i] == cur->next){return addr[i];}}cur = cur->next;} return NULL;
}代码实现二：
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast) // 再次相遇{struct ListNode* start = head; // start 从起始结点出发struct ListNode* meet = slow; // meet 从相遇结点出发while (start != meet){start = start->next;meet = meet->next;}return start; // 或者 return meet;}}return NULL;
}分析：
其中
L表示指针从头结点走到入环第一个结点所需要的步数，x表示慢指针走到入环的第一个结点后，与快指针再次相遇所需走的步数，C则表示环的长度。从起点出发到再次相遇，慢指针 slow 走的步数为 L + x，快指针 fast 走的步数为 L + k * C + x（k >= 1），又因为 slow 每次走一步，fast 每次走两步，所以有：2(L + x) = L + k * C + x，即 L = k * C + x ==> L = (k - 1)C + x。
由此得出一个结论：在链表有环的前提下，一个指针从起始结点开始走，另一个指针从再相遇结点开始走，两个指针每次走一步，最终这两个结点会在入环的第一个结点相遇。
代码实现三：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode *tailA = headA, *tailB = headB;int lenA = 1, lenB = 1;while (tailA->next != NULL){++lenA;tailA = tailA->next;}while (tailB->next != NULL){++lenB;tailB = tailB->next;}if (tailA != tailB){return NULL;}int gap = abs(lenA - lenB);struct ListNode *longCur = headA, *shortCur = headB;if (lenA < lenB){longCur = headB;shortCur = headA;}for (int i = 0; i < gap; ++i){longCur = longCur->next;}while (longCur != shortCur){longCur = longCur->next;shortCur = shortCur->next;}return longCur;
}
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){// 转换成求相交结点struct ListNode* headB = slow->next;slow->next = NULL;return getIntersectionNode(head, headB);}}return NULL;
}