Linked List Cycle II--LeetCode

不念不忘少年蓝@ 2022-08-07 10:57 8阅读 0赞

这道题是Linked List Cycle的扩展，就是在确定是否有cycle之后还要返回cycle的起始点的位置。从Linked List Cycle中用的方法我们可以得知a=kc-b（不了解的朋友可以先看看Linked List Cycle）。现在假设有两个结点，一个从链表头出发，一个从b点出发，经过a步之后，第一个结点会到达cycle的出发点，而第二个结点会走过kc-b，加上原来的b刚好也会停在cycle的起始点。如此我们就可以设立两个指针，以相同速度前进知道相遇，而相遇点就是cycle的起始点。算法的时间复杂度是O(n+a)=O(2n)=O(n)，先走一次确定cycle的存在性并且走到b点，然后走a步找到cycle的起始点。空间复杂度仍是O(1)。代码如下：

public ListNode detectCycle(ListNode head)  
        {  
            if(head == null || head.next == null)  
                return null;  
            ListNode walker = head.next;  
            ListNode runner = head.next.next;  
            while(runner!=null && walker!=runner)  
            {  
                walker = walker.next;  
                if(runner.next!=null)  
                    runner = runner.next.next;  
                else  
                    runner = null;  
            }  
            if(runner == null)  
                return null;  
            runner = head;  
            while(walker!=runner)  
            {  
                walker = walker.next;  
                runner = runner.next;  
            }  
            return walker;  
        }

发表评论取消回复

表情：

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

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

相关阅读

相关 Linked List Cycle

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

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

相关 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 赞/ 146 阅读

相关 Leetcode: Linked List Cycle

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

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

相关 #141 Linked List Cycle

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

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

相关 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 赞/ 145 阅读

相关 [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 赞/ 70 阅读

相关 LeetCode141—Linked List Cycle

原题 [原题链接][Link 1] > Given a linked list, determine if it has a cycle in it. > > Fol

淡淡的烟草味﹌/ 2022年07月16日 00:11/ 0 赞/ 143 阅读

相关 141.linked list cycle

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

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

相关【leetcode82】Linked List Cycle

题目描述：判断有序list是不是环要求：时间复杂度o（n）原文描述： Given a linked list, determine if it

た入场券/ 2022年04月11日 06:41/ 0 赞/ 123 阅读

相关 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 赞/ 224 阅读