Given a linked list, return the node where the cycle begins.

太过爱你忘了你带给我的痛 2022-05-26 04:25 75阅读 0赞

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.  
Follow up:  
Can you solve it without using extra space?  
给定一个链表，判断是否有环，如果没有环，直接返回null。（解决这个问题而不需要额外的空间）  
![这里写图片描述][70]

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
    public class Solution { 
        public ListNode detectCycle(ListNode head) {
            if(head == null)
                return head;
            ListNode slow = head;
            ListNode fast = head;
            boolean isCircle = false;
            //快慢指针判断是否有环
            while(fast != null && fast.next != null && fast.next.next != null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    isCircle = true;
                    break;
                }
            }
            //环不存在
            if(!isCircle){
                return null;
            }
            //其中一个指针从头开始遍历，下一次两个指针相遇的结点就是环的入口
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }

[70]: /images/20220526/995aec81366549efb6ce32401c5e31c0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，75人围观）

还没有评论，来说两句吧...

相关阅读

相关 Linked List Cycle

链表中环的入口位置 Linked List Cycle II Total Accepted: 10308 Total Submissions: 33751 [

阳光穿透心脏的1/2处/ 2022年08月26日 13:19/ 0 赞/ 189 阅读

相关 141. Linked List Cycle

Problem: > Given a linked list, determine if it has a cycle in it. > Follow up: > C

冷不防/ 2022年08月21日 00:03/ 0 赞/ 161 阅读

相关 Leetcode: Linked List Cycle

题目： Given a linked list, determine if it has a cycle in it. 思路分析：利用快慢指针slow，fast。

妖狐艹你老母/ 2022年08月07日 11:56/ 0 赞/ 27 阅读

相关 Linked List Cycle--LeetCode

题目： Given a linked list, determine if it has a cycle in it. Follow up: Can you solv

谁借莪１个温暖的怀抱￠/ 2022年08月07日 10:55/ 0 赞/ 19 阅读

相关 #141 Linked List Cycle

这是一道简单的中级题，本想上道题做完就不做了的，结果看到这个好简单就还是做一下吧~ [\141 Linked List Cycle][141 Linked List Cycl

素颜马尾好姑娘i/ 2022年08月02日 04:59/ 0 赞/ 156 阅读

相关 141. Linked List Cycle

Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it w

怼烎@/ 2022年07月29日 08:50/ 0 赞/ 162 阅读

相关 [leetcode] Linked List Cycle

Problem: Given a linked list, determine if it has a cycle in it. Follow up: Can you

朴灿烈づ我的快乐病毒、/ 2022年07月17日 02:37/ 0 赞/ 87 阅读

相关 141.linked list cycle

/\ 判断输入的链表是否是循环链表思路：利用快慢指针，一个是p = p->next;另外一个是q = q->next；如果两个指针相遇了，则说明是循环链表 \/

男娘i/ 2022年06月10日 14:11/ 0 赞/ 172 阅读

相关 Given a linked list, return the node where the cycle begins.

Given a linked list, return the node where the cycle begins. If there is no cycle, retur

太过爱你忘了你带给我的痛/ 2022年05月26日 04:25/ 0 赞/ 76 阅读

相关 141. Linked List Cycle

1. 原始题目 Given a linked list, determine if it has a cycle in it. To represent a cycle

水深无声/ 2021年12月10日 08:49/ 0 赞/ 245 阅读