营销型企业网站策划方案,燃灯seo,网页推广平台,个人现在可以做哪些网站题目链接#xff1a;142.环形链表II
题目描述#xff1a; 给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。 如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环…题目链接142.环形链表II
题目描述 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例 1 输入head [3,2,0,-4], pos 1
输出返回索引为 1 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出返回 null
解释链表中没有环。提示 链表中节点的数目范围在范围 [0, 104] 内-105 Node.val 105pos 的值为 -1 或者链表中的一个有效索引 思路参考环形链表I 依旧使用快慢指针解决 参考环形链表I 快慢指针一定会在环形链表中相遇。 以示例1为例 head为链表的头结点meet为快慢指针在环中的相遇点 由图可以初步判断 meet到入环的初始结点的距离等于head到入环的初始结点的距离。 证明相遇点到入环起始结点的距离 链表头结点到入环起始结点的距离 L为头结点到入环初始结点的距离E为入环的初始结点M为快慢指针相遇结点X入环的初始结点到相遇点的距离R为环的周长R-X为相遇点到头结点的距离。 在快慢指针相遇时fast所走的路程为LXnRslow所走的路程为LX 又因为慢指针走一步快指针走两步有以下公式 2*慢指针的路程 快指针的路程 代入快慢指针路程可以得到 L (n-1)R(R-X)n 123... 当n等于1时即相遇时快指针刚好绕环一圈则L R-X 故相遇点到入环起始结点的距离 链表头结点到入环起始结点的距离 代码实现 ListNode* slow head;ListNode* fast head;ListNode* meet NULL;while(fast fast-next){slow slow-next;fast fast-next-next;if (slow fast){meet slow;break;}} 定义快慢指针找到相遇结点meet找到后跳出循环。 ListNode* left head;ListNode* right meet;while(right){ if (left right){return left;}left left-next;right right-next;} 找到相遇点后让头结点和相遇点同时往后遍历找到入环的起始结点若相遇点为空直接返回NULL。
完整代码 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode* slow head;ListNode* fast head;ListNode* meet NULL;while(fast fast-next){slow slow-next;fast fast-next-next;if (slow fast){meet slow;break;}}ListNode* left head;ListNode* right meet;while(right){ if (left right){return left;}left left-next;right right-next;}return NULL;
}
