首页 > 代码库 > [leetcode]Linked List Cycle II

[leetcode]Linked List Cycle II

2024-07-12 22:03:24   223人阅读

Linked List Cycle II

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

Follow up:
Can you solve it without using extra space?

算法

思路1：

最土的双指针算法，先检测是否有环，如果有，则用一只指针detect逐个定位节点，用另一个指针loop，循环测试。时间复杂度为O(n*n)，空间为O(1)，but

有一个疑问：

如何防止死循环？

不实现了，比较简单。

 

思路2：

同[leetcode]Linked List Cycle的思路2，hash，一次遍历，代码简单，空间复杂度O(n)，时间复杂度O(n)

 1 public class Solution { 2     public ListNode detectCycle(ListNode head) { 3         if(head == null) return null; 4         ListNode tem = new ListNode(0); 5         tem.next = head; 6         Map<ListNode,ListNode> hash = new HashMap<ListNode,ListNode>(); 7         while(true){ 8             if(tem.next == null) return null; 9             if(hash.get(tem.next) != null) return tem.next;10             hash.put(tem.next,tem);11             tem = tem.next;12         }13     }14 }

 

思路3：

同样采用快慢指针，测试到有环，则慢指针回到head，快指针还指向第一次相遇的节点，然后两个指针齐步走，当两指针再次相遇的时候，则相遇点即为环的起点，时间复杂度O(n)，空间复杂度O(1)，但是需要两遍遍历。

这个算法有点高大上，在leetcode中有人专门用一个专题进行了详细的讲解(链接偶尔打不开)，也可以参考 Floyd’s cycle finding algorithm我还没看，哈哈

 

不啰嗦，代码如下:

 1 public class Solution { 2     public ListNode detectCycle(ListNode head) { 3         if(head == null) return null; 4         ListNode fast = head; 5         ListNode slow = head; 6         while(true){ 7             if(fast.next == null || fast.next.next == null) return null; 8             fast = fast.next.next; 9             slow = slow.next;10             if(fast == slow){11                 slow = head;12                 break;13             }14         }15         while(fast != slow){16             fast = fast.next;17             slow = slow.next;18         }19         return fast;20     }21 }


联系
我们