福田做网站福田网站建设福田建网站500,请别人做网站注意事项,gps建站步骤视频,有固定ip怎么建设网站目录
一、相交链表
二、环形链表
三、环形链表 || 一、相交链表
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。
图示两个链表在节点 c1 开始相交#xff1a; 题目数据…目录
一、相交链表
二、环形链表
三、环形链表 || 一、相交链表
给你两个单链表的头节点 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 CC 表示环的长度然后 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 xk 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;
}
