leetcode142 环形链表II

举报
兔老大 发表于 2021/04/20 00:05:43 2021/04/20
【摘要】 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 说明:不允许修改给定的链表。   示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:...

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

 

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。


示例 2:

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。


示例 3:

输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

思路:

慢指针一次一步,快指针一次两步。能相遇就是有环,反之没有环。

让一个指针从头走,另一个从相遇点开始走,然后再次相遇的地方就是入环点,不明白的画一画,想一想操场跑步就明白了。


  
  1. /**
  2. * Definition for singly-linked list.
  3. * class ListNode {
  4. * int val;
  5. * ListNode next;
  6. * ListNode(int x) {
  7. * val = x;
  8. * next = null;
  9. * }
  10. * }
  11. */
  12. public class Solution {
  13. private ListNode getIntersect(ListNode head) {
  14. ListNode tortoise = head;
  15. ListNode hare = head;
  16. while (hare != null && hare.next != null) {
  17. tortoise = tortoise.next;
  18. hare = hare.next.next;
  19. if (tortoise == hare) {
  20. return tortoise;
  21. }
  22. }
  23. return null;
  24. }
  25. public ListNode detectCycle(ListNode head) {
  26. if (head == null) {
  27. return null;
  28. }
  29. ListNode intersect = getIntersect(head);
  30. if (intersect == null) return null;
  31. ListNode ptr1 = head;
  32. ListNode ptr2 = intersect;
  33. while (ptr1 != ptr2) {
  34. ptr1 = ptr1.next;
  35. ptr2 = ptr2.next;
  36. }
  37. return ptr1;
  38. }
  39. }

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/103435803

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。