环形链表相关的练习

目录

一、相交链表

二、环形链表

三、环形链表 ||

---

---

一、相交链表

给你两个单链表的头节点 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;
}

问题（前提是链表带环）：

1. 快慢指针从相同的起始位置出发，慢指针 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。

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;
}