leetcode 142. 环形链表 2

秒速五厘米 2023-02-09 11:55 6阅读 0赞

哈哈，这题和环形链表1差不多 ，链表1详情参见  [https://blog.csdn.net/a66666\_/article/details/105211023][https_blog.csdn.net_a66666_article_details_105211023]

解法1. 快慢指针 （建议不要直接复制到leetcode，会报错，自己手打一遍）

时间复杂度O(N)  空间复杂度O(1)

> java:
> 
> public ListNode detectCycle(ListNode head) \{
> 
>         ListNode walker = head;
> 
>         ListNode runner = head;
> 
>         while (runner != null && runner.next != null) \{
> 
>             walker = walker.next;
> 
>             runner = runner.next.next;
> 
>             if (walker == runner) \{
> 
>                 ListNode walker2 = head;
> 
>                 while (walker != walker2) \{
> 
>                     walker = walker.next;
> 
>                     walker2 = walker2.next;
> 
>                 \}
> 
>                 return walker;
> 
>             \}
> 
>         \}
> 
>         return null;
> 
>     \}
> 
> javsScript:
> 
> var detectCycle = function(head) \{
> 
>     let slower = head;
> 
>     let flast = head;
> 
>     while(flast != null && flast.next != null) \{
> 
>         slower = slower.next;
> 
>         flast = flast.next.next;
> 
>         if(slower === flast) \{
> 
>             let slower2 = head;
> 
>             while(slower != slower2) \{
> 
>                 slower = slower.next;
> 
>                 slower2 = slower2.next;
> 
>             \}
> 
>             return slower;
> 
>         \}
> 
>     \}
> 
>     return null;
> 
> \};

相比 环形链表1的解法多了下方的代码

> ListNode walker2 = head;
> 
>                 while (walker != walker2) \{
> 
>                     walker = walker.next;
> 
>                     walker2 = walker2.next;
> 
>                 \}

因为环形链表1快慢指针相遇的节点**并不是连接的那个节点**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E2NjY2Nl8_size_16_color_FFFFFF_t_70][]

如图所示，p为快慢指针相遇节点，q为连接节点，而连接节点由公式 a+2b+c == 2(a+b)可推出a == c

解法二：哈希表

时间复杂度O（N），空间复杂度O(N)

> java描述：
> 
> public ListNode detectCycle(ListNode head) \{
> 
>         Set<ListNode> node = new HashSet<ListNode>();
> 
>         while (head != null) \{
> 
>             if (node.contains(head)) \{
> 
>                 return head;
> 
>             \}
> 
>             node.add(head);
> 
>             head = head.next;
> 
>         \}
> 
>         return null;
> 
>     \}
> 
> javaScript描述：
> 
> var detectCycle = function(head) \{
> 
>     let nodes = new Set();
> 
>     while(head) \{
> 
>         if (nodes.has(head)) return head;
> 
>         nodes.add(head);
> 
>         head = head.next;
> 
>     \}
> 
>     return null;
> 
> \};

[https_blog.csdn.net_a66666_article_details_105211023]: https://blog.csdn.net/a66666_/article/details/105211023
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E2NjY2Nl8_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200518193214466.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E2NjY2Nl8=,size_16,color_FFFFFF,t_70