【Day 11 】2022-11-11 - 142. 环形链表 II

[azl397985856]

142. 环形链表 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/linked-list-cycle-ii/

前置知识

暂无

题目描述

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

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

进阶：

你是否可以使用 O(1) 空间解决此题？

[mayloveless]

思路

1. 通过哈希表存储节点，遍历链表，如果遇到相同的node，即为入口。空间和时间复杂度O(n)
2. 快慢指针遍历链表，快指针是慢指针走过节点的2倍，当相遇时，经过推导，相遇节点到入环的距离和 head到入环的距离相等。所以从head和相遇节点各自移动到相等，则是入环节点

代码

var detectCycle = function(head) {
    let fast = hasCycle(head);
    if (!fast) return null;

    let slow = head;
    while(slow) {
        if (slow === fast) return slow;
        slow = slow.next;
        fast = fast.next;
    }
    return null;
};

var hasCycle = function(head) {
    if (!head) return false;

    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast === slow) return fast;
    }
    return null;
};

复杂度

时间O(n) 空间O(1)

[zywang0]

Code

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        slow = head;
        if(fast == null || fast.next == null){
            return null;
        }
        while(slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

[yin02]

思路

双指针第一次相遇，第一种结果： fast 指针走过链表末端，说明链表无环，直接返回 null；第二种结果： 当fast == slow时， 两指针在环中 第一次相遇 ，双指针第二次相遇：

slow指针 位置不变 ，将fast指针重新 指向链表头部节点 ；slow和fast同时每轮向前走 11 步；双指针第二次相遇：

slow指针 位置不变 ，将fast指针重新 指向链表头部节点 ；slow和fast同时每轮向前走 11 步；

代码

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

复杂度分析 时间复杂度 O(N)O(N) ：第二次相遇中，慢指针须走步数 a < a + ba<a+b；第一次相遇中，慢指针须走步数 a + b - x < a + ba+b−x<a+b，其中 xx 为双指针重合点与环入口距离；因此总体为线性复杂度； 空间复杂度 O(1)O(1) ：双指针使用常数大小的额外空间。

[FlipN9]

/**
    找到 LL 环的入口, 如果无环, 返回 null

    思路: 快慢指针, 快指针有环会追上慢指针 相遇

      a     b 
    -----------|    假设慢指针走 x 步, 快指针是 2x, 
        |      |    head 到环入口有 a 个节点, 环有 b + c 个节点
        -------| c          

    x = a + b, 2x = a + b + c + b 
    2a + 2b = a + c + 2b
    a = c

    所以 当 slow fast 相遇后, 我们重新用 slow 指向 head
    slow 和 fast 同时同速移动, 他们会在环的入口处相遇

    TC: O(n), SC: O(1)
*/
class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null)
            return null;

        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        // 无环
        if (fast == null || fast.next == null)
            return null;
        // 有环
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

[wtdcai]

代码

class Solution(object):
    def detectCycle(self, head):
        slow,fast  = head, head
        while True:
            if not (fast and fast.next): 
                return None
            fast, slow = fast.next.next, slow.next
            if fast == slow: 
                break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

复杂度分析

O(N)
O(1)

[Alyenor]

function detectCycle(head: ListNode | null): ListNode | null {
    if(!head || !head.next) return null
    let quick=head.next, slow=head
    while(quick){
        quick=quick.next
        slow=slow.next

        if(!quick) return null

        quick=quick.next

        if(quick===slow) {
            slow = head
            quick = quick.next
            while(quick !== slow){
                slow=slow.next
                quick=quick.next
            }
            return slow
        }

    }
    return null
};

[bookyue]

thought

  a     b 
-----------| <- They will meet at here   
    |      |
    -------| c    Thanks to @FlipN9

2 * slow pointer travel distance = fast pointer travel distance
=> 2 * (a + b) = a + (b + c) + b (if the circle is big enough)
=> a = c
otherwise 
=> 2 * (a + b) = a + N * (b + c) + b
=> a + b = N * (b + c)
=> a = (N - 1) * b + N * c
=> claim K = N - 1
=> a = K * b + (K + 1) * c
=> a = K * (b + c) + c

code

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        do {
            if (fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        slow = head;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

[MDGE]

var detectCycle = function(head) { let m = new Map() let cur = head while(cur){ if(m.get(cur)){ return cur }else{ m.set(cur,true) cur = cur.next } } return null };

[buer1121]

class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:

    ###思路，快慢指针，相遇则说明有环,然后fast再从头走，再次相遇即是环的第一个节点
    if not head:
        return None
    slow,fast=head,head
    while slow and fast:
        slow=slow.next
        if fast.next:
            fast=fast.next.next
        else:return None

        if slow==fast:
            break
    fast=head
    while slow and slow!=fast:
        slow=slow.next
        fast=fast.next
    return slow

[xiaomingshixiaotang]

思路

1. 用一个数组存储已经遍历过的，未成环的节点
2. 在遍历每个节点时，比较该节点的下一节点与数组中存储的之前的节点，判断是否相等，如相等，则返回该节点的下一节点
3. 遍历结束，返回NULL

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        vector<ListNode*> noloopNode;

        ListNode* tem = head;
        while(tem)
        {
            if(!noloopNode.empty())
            {
                for(ListNode* node : noloopNode)
                {
                    if(node == tem->next)
                    {
                        return node;
                    }
                }
            }
            noloopNode.push_back(tem);
            tem = tem->next;
        }

        return NULL;
    }
};

复杂度分析

• 时间复杂度：O(n*n)
• 空间复杂度：O(n)

[954545647]

思路

双指针 or 哈希

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 var detectCycle = function(head) {
  if (head === null) {
      return null;
  }
  let slow = head, fast = head;
  while (fast !== null) {
      slow = slow.next;
      if (fast.next !== null) {
          fast = fast.next.next;
      } else {
          return null;
      }
      if (fast === slow) {
          let ptr = head;
          while (ptr !== slow) {
              ptr = ptr.next;
              slow = slow.next;
          }
          return ptr;
      }
  }
  return null;
};

复杂度分析

• 空间复杂度 O(1)
• 时间复杂度 O(n)

[BruceZhang-utf-8]

思路

• 考虑使用map记录节点，map中包含遍历节点时，即说明该节点就是环形链表的入口节点

关键点

代码

• 语言支持：Java

Java Code:

/**
 * 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) {
         //定义一个返回的节点
        ListNode resultNode=null;
        //定义一个遍历节点
        ListNode curr=head;
        //声明一个map，用于存储节点
        HashMap<ListNode, ListNode> map = new HashMap<ListNode, ListNode>();
        while(curr!=null){
            if(!map.containsKey(curr)){
                map.put(curr,curr.next);
            }else{
                resultNode=curr;
                break;
            }
            curr=curr.next;
        }
        return resultNode;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[JancerWu]

思路

快慢指针，设起始点到环入口的距离，环入口点到快慢指针相遇点的距离，快慢指针相遇点到环入口点的距离分别为为a、b、c，则有a + b + n (b + c) = 2 (a + b), 由此可以推出 a = c + (n - 1) * (b + c), 即从起始点出发，和慢指针相遇点即为环的入口点

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return head;
        ListNode slow = head, fast = head.next;
        while (slow != fast) {
            slow = slow.next;
            if (fast != null) fast = fast.next;
            if (fast != null) fast = fast.next;
        }
        if (slow == null) return null;
        ListNode ans = head;
        slow = slow.next; // 注意需要踏上这一步，长度才开始生效。
        while (ans != slow) {
            ans = ans.next;
            slow = slow.next;
        }
        return ans;
    }
} 

复杂度

• 时间：O(n)
• 空间：O(1)

[chiehw]

基本思路：

简化模型，最后求得快慢指针相交点和链表相交点的关系 a=c+(n-1)(b+c)

大致步骤：

1. 打表。
2. 使用 head 指针遍历链表，并设置快指针每次走两步。
3. 如果没有环 head 会等于 NULL，否则会一直循环。
4. 如果快慢指针移动到相交的地方， 定义 ptr 指针从链表头开始，直到慢指针和 ptr 指针重合，退出循环。
5. 返回 head 指针。

代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL){
            return NULL;
        }

        ListNode *fast, *ptr;
        fast = ptr = head;

        while(head != NULL){
            head = head->next;
            if(fast->next != NULL && fast->next->next != NULL){
                fast = fast->next->next;
            }else{
                head = NULL;
                break;
            }

            if(fast == head){
                while(ptr != head){
                    ptr = ptr->next;
                    head = head->next;
                }
                break;
            }
        }

        return head;
    }
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[heng518]

class Solution { public: ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast)
        {
            slow = head;

            while(slow != fast)
            {
                slow = slow->next;
                fast = fast->next;
            }

            return slow;
        }
    }
    return NULL;
}

};

[chenming-cao]

解题思路

快慢指针。fast每次前进两格，slow每次前进一格。如果无环则fast率先到达尾部null。如果有环，则在相遇时重置fast为head，每次前进一格，再次相遇节点即为开始入环的第一个节点。

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;

        do {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == null || fast.next == null) return null;
        } while (fast != slow);

        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }       
        return fast;
    }
}

复杂度分析

令n为链表长度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[yoco323]

解题思路

space O(N), use hashset to store the listNode, when there is exist same listnode in hashset, return this node.

space O(1), slow pointer moves 1 step, fast pointer moves 2 steps.

代码

/**
 * 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) {
        // check whether head is null
        if(head == null){
            return null;
        }
        ListNode slow = head, fast = head;
        while(fast != null){
            slow = slow.next;
            if(fast.next != null){
                fast = fast.next.next;
            }
            else{
                return null;
            }
            if(fast == slow){
                ListNode ptr = head;
                while(ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

[whoam-challenge]

思路

快慢指针。定义两个指针，快指针：一次移动两步，慢指针：一次移动一步。 1）如果移动过程中，快指针指向null或者快指针.next指向null，则没有环，return None。 2）如果上述情况不会发生，则有环。fast与slow第一次相遇（注意相遇不一定就相遇在环入口），则fast 走了2s步，slow走了s步，假设环前有a个节点，环内有b个节点。则2s-s=nb；于是s=nb 如何让指针指向环入口呢？只要slow指针再走a步即可。 3）让fast回到头部，然后fast每次移动一步，slow每次移动一步，如果fast与slow相遇，则slow一共走了a+nb步，此时指向环的入口。返回slow即可。

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head, head
        while True:
            if not(fast and fast.next):
                return None
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        fast = head
        while fast!= slow:
            fast = fast.next
            slow = slow.next
        return slow 

复杂度分析

-时间复杂度：O(N)

-空间复杂度：O(1)

[Jetery]

142. 环形链表 II

思路 快慢指针

令快指针fast步长为2, 慢指针slow步长为1
假设链表有环, 记链表头到开始入环的第一个节点之前的节点路程为x, 整个环路长度为cycle, 快慢指针相遇点 到 入环的第一个节点的路程为y
由于fast速度是slow两倍, 就有式子2 * (x + cycle -y) = x + n * cycle - y
化简得x = (n - 2) * cycle + y 由于cycle是环路长度, 可以忽略, 得到x = y
即相遇后慢指针slow从头出发, 快指针fast在相遇点出发, 步长都为1, 会再次在入环点相遇

代码 (cpp)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }

        if (fast == nullptr || fast->next == nullptr) return nullptr;
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[zhiyuanpeng]

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = head
        pool = set()
        while p:
            if p in pool:
                return p
            else:
                pool.add(p)
            p = p.next
        return None

[klspta]

思路

查找入环点标准解法

代码

    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode fast = head.next.next;
        ListNode slow = head.next;

        while(fast != null && fast.next != null && fast != slow){
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast == null || fast.next == null){
            return null;
        }

        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

[xuanaxuan]

双指针

具体算法：

定义一个 fast 指针,每次前进两步,一个 slow 指针,每次前进一步

当两个指针相遇时(注意相遇不一定就相遇在环入口)，将 fast 指针重定位到链表头部,同时 fast 指针每次只前进一步，slow 指针继续前进,每次前进一步

当两个指针再次相遇时,当前节点就是环的入口

代码

if (head == null || head.next == null) return null;
let fast = (slow = head);
do {
  if (fast != null && fast.next != null) {
    fast = fast.next.next;
  } else {
    fast = null;
  }
  slow = slow.next;
} while (fast != slow);
if (fast == null) return null;
fast = head;
while (fast != slow) {
  fast = fast.next;
  slow = slow.next;
}
return fast;

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[testplm]

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 设定快慢指针，有环的链表最终会相遇
        slow = fast = head
        while fast and fast.next:
            slow  = slow .next
            fast = fast.next.next
            if slow==fast:
                break
        else: return None
        while head != slow:
            head,slow = head.next,slow.next
        return head

• Time: O(n)
• Space:O(1)

[miduoliu]

Thought: Use two pointer, fast and slow pointer to check if there is a cycle in linkedlist. After they met, use another pointer to start from the beginning, traverse with slow pointer in same pace. When they met, the node would be the cycle entrance.

Code:

public ListNode cycleDetect(ListNode head) {
        if (head == null || head.next == null)
            return null;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                return slow;
        }
        return null;
    }
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode newL = head;
        ListNode cycle = cycleDetect(head);
        if (cycle == null) return null;
        while (newL != cycle) {
            newL = newL.next;
            cycle = cycle.next;
        }
        return newL;
    }

[amazeding]

思路

• 快慢指针，快指针走两步，慢指针走一步

  代码

  public class Solution {
  public ListNode detectCycle(ListNode head) {
      //快慢指针，快指针走两步，慢指针走一步
      ListNode fast = head;
      ListNode slow = head;
      while(fast != null && fast.next != null) {
          fast = fast.next.next;
          slow = slow.next;
          if(fast == slow) {
              //第一次相遇,继续判断
              fast = head;
              while (fast != slow) {
                  fast = fast.next;
                  slow = slow.next;
              }
              return fast;
          }
      }
      return null;  
  }
  }

  复杂度分析

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

[Abby-xu]

思路

1. 快慢指针走，如果相遇则是在环上，没有则是没有交点
2. 从头走head继续走slow，之后的再次相遇就是在交点

代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        else:
            return None
        while head != slow:
            slow = slow.next
            head = head.next
        return head

复杂度

O(n) / O(1)

[A-pricity]

/ **
 * 解题思路：快慢指针法
 * 快指针和慢指针相遇在环上，则有交点，否则无交点
 * 从头继续遍历slow，再次相遇则为交点
 * 根据：
 * f=2s （快指针每次2步，路程刚好2倍）
 * f = s + nb (相遇时，刚好多走了n圈）
 * 推出：s = nb
 * 从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
 * 如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if(head == null || head.next == null ) return null;
    let fast = (slow = head);
    do{
        if(fast != null && fast.next != null){
            fast = fast.next.next;
        }else{
            fast = null;
        }
        slow = slow.next;
    }while(fast != slow);

    if(fast == null) return null;
    fast = head;
    while(fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    return fast;

};

[yuexi001]

思路

创建哈希表，依次遍历每个结点加入哈希表中，当发现哈希表中存在该结点，则该结点为环的入口，否则遍历结束返回null

代码

C++ Code:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
       ListNode *cur = head;
        set<ListNode*>st;
        while(cur != nullptr){
            if(st.find(cur) != st.end())
                return cur;
            st.insert(cur);
            cur = cur->next;           
        }
        return nullptr;
    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[allenfeng666]

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

[Dark-volute]

思路

• 遍历整个链表,同时将每个节点都插入哈希表,
• 如果当前节点在哈希表中不存在,继续遍历,
• 如果存在,那么当前节点就是环的入口节点

let data = new Set();
while (head) {
  if (data.has(head)) {
    return head;
  } else {
    data.add(head);
  }
  head = head.next;
}
return null;

复杂度分析

时间复杂度：$O(N)$ 空间复杂度：$O(N)$

[Whisht]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while True:
            if not fast or not fast.next:
                return None
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        fast = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

复杂度

• 时间复杂度： $O(n)$
• 空间复杂度： $O(1)$

[liuajingliu]

解题思路

从head开始快慢指针，快指针每次两步，慢指针每次一步，第一次相遇时将快指针回到head，改为每次前进一步，第二次相遇点为环起始点

代码实现

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if(head === null || head.next === null) return null;
    // 定义快慢两个指针、只想链表头部
    let fast = head;
    let slow = head;
    // 快指针走两步，满指针走一步
    do {
        if (fast !== null && fast.next !== null) {
            fast = fast.next.next;
        } else {
            fast = null
        }
        slow = slow.next;
    } while(fast !== slow)
    if (fast === null) return null;
    // 相遇后将快指针指向链表头部
    fast = head;
    while(fast !== slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
};

复杂度分析

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

[tiandao043]

思路

快慢指针，第一次相遇时，快指针多跑n-1圈多，半个弧D，此时fast重置到head，步长为1，再次相遇时，自己走了直线部分L，由上次经验(L+C)2=L+n(D+C)+c可推L=(n-1)(C+D)+D,slow正好走的就是公式右半部分，二者在交汇处相遇。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow=head;
        ListNode *fast=head;
        int i=0;
        if(fast!=nullptr&&fast->next!=nullptr && fast->next->next!=nullptr){
            slow=slow->next;
            fast=fast->next->next; 
        }else{
            return NULL;
        }
        while(fast!=slow && fast!=nullptr && slow!=nullptr){
            slow=slow->next;
            if (fast != nullptr && fast->next != nullptr) {
            fast=fast->next->next;       }
            else{fast=nullptr;}     
        }

        if(fast==slow){
            fast=head;
            while(fast!=slow){
                slow=slow->next;
                fast=fast->next;  
            }
        }
        return fast;
    }
};

简化

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *f=head,*s=head;
        while(f!=nullptr&&f->next!=nullptr){
            f=f->next->next;
            s=s->next;
            if(f==s){
                f=head;

            while(f!=s){
                f=f->next;
                s=s->next;
            }            
            return f;}
        }
        return NULL;
    }
};

复杂度

O(n) O(1)

[A-PolarBear]

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;

        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast){
                ListNode *tmp = head;
                while(tmp!=slow){
                    tmp = tmp->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

[GG925407590]

解题思路 从head开始快慢指针，快指针每次两步，慢指针每次一步，第一次相遇时将快指针回到head，改为每次前进一步，第二次相遇点为环起始点

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;
        while (true) {
            if (fast == nullptr || fast->next == nullptr) return nullptr;
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }
        fast = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

复杂度分析 时间复杂度：O(N) 空间复杂度：O(1)

[Weisday]

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow. Next;
            fast = fast.next.next;
            // 第一次相遇
            if(slow == fast){
                fast = head;
                while(true){
                    // 第二次相遇
                    if(slow == fast) return slow;
                    slow = slow. Next;
                    fast = fast. Next;
                }
            }
        }
        return null;
    }
}

[AtaraxyAdong]

思路

方法一：HashSet，简单粗暴

方法二：快慢指针，参考答案

定义两个指针：fast、slow，步长分别为2、1，当slow入环时，fast走了slow的两倍距离（也就是从head到入环口距离的两倍），fast要追上slow，需要追的距离为：环的长度 - head到入环口的长度，所以可知，第一次相遇时，slow从相遇点再回到入环口的长度等于slow从head到入环口的长度

代码

方法一：集合

public class Solution {
    public ListNode detectCycle(ListNode head) {

        Set<ListNode> set = new HashSet<>();
        ListNode pointer = head;
        while (pointer != null) {

            if (set.contains(pointer)) return pointer;

            set.add(pointer);
            pointer = pointer.next;

        }
        return null;
    }
}

方法二：快慢指针

class Solution {
    public ListNode detectCycle(ListNode head) {

        ListNode fast = head, slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

复杂度分析

集合：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

快慢双指针：

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

[gsw9818]

思路

快慢法

代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:

        fast = head
        slow = head

        if not head or not head.next:
            return

        while True:
            if not fast or not fast.next: return
            fast = fast.next.next
            slow = slow.next
            if fast == slow : 
                break

        fast = head

        while fast != slow:
            fast = fast.next
            slow = slow.next

        return fast

算法复杂度

时间O(n),空间O(1)

[xqmmy]

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

[snmyj]

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        if(head == NULL) return head;
        ListNode* slow = head, *fast = head, *ret = head;
        while(fast && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                while(ret != slow)
                {
                    ret = ret-> next;
                    slow = slow-> next;
                }
                return ret;
            }
        }
        return NULL;
}
};

[paopaohua]

思路

快慢指针，找到交点之后，将快指针放回head，步长变1

代码

/**
* 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 null;
ListNode fast = head;
ListNode low = head;
while(fast != null){
low = low.next;
if(fast.next != null){
fast = fast.next.next;
}else{
return null;
}
if(fast == low){
ListNode fast1 = head;
while(fast1 != low){
fast1 =fast1.next;
low = low.next;
}
return fast1;
}
}
return null;

}

}

### 复杂度
- 时间：o(n)
- 空间：o(1)

[RestlessBreeze]

思路

遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环

代码

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

复杂度

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

[zhuzhu096]

class Solution { public: ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head;

while(fast && fast->next){
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast){
        fast = head;

    while (slow != fast){
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
    }
}
return NULL;

} };

[AstrKing]

思路

快慢指针，使用两个指针，一个移动1次，一个移动2次，如果存在环，那么终究会相遇

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

[Alexno1no2]

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:

        slow, fast = head, head
        while fast  and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break;
        if not fast or not fast.next: 
            return None
        fast = head
        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow

[rzhao010]

Thoughts

If no loop, fast will hit the tail of list; if loop. exists, fast will catch slow eventually. Once fast caught slow, we use another pointer to find the node cycle begins

Complexity

Time: O(n) Space: O(1)

Code

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;

        while (true) {
            if (fast == null || fast.next == null) return null;// no loop
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) break; // fast caught slow in the loop
        }
        fast = head;
        while (slow != fast) {
            // once slow == fast, loop ends
            // fast will be at the point cycle begins
            slow = slow.next;
            fast = fast.next;
        }
        return fast;

    }
}

[sclihuiming]

func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        return nil
    }
    fast = head
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }
    return fast
}

[steven72574]

思路：快慢指针，当快慢指针相遇时，快指针再从头开始走，再次相遇则是环入口点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)return null;
        ListNode fast = head,slow=head;

        while(true){
            if(fast==null||fast.next==null)return null;
            fast=fast.next.next;
            slow = slow.next;
            if(fast==slow)break;
        }
        fast=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}

time o(n) space O(1)

[neado]

思路

快慢指针，经过推断，得出相交后，再置一个指针到开始位置，以慢指针的速度走，两者相交位置寄环开始处

代码

/**
 * 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 null;
        }
        ListNode fast=head,slow=head;
        while(fast!=null){
            slow=slow.next;
            if(fast.next!=null){
                fast=fast.next.next;
            }else{
                return null;
            }

            if(fast==slow){
                ListNode ft=head;

                while(ft!=slow){
                    ft=ft.next;
                    slow=slow.next;
                }
                return ft;
            }

        }
        return null;
    }
}

算法复杂度

TIME:O(n) SPACE:O(1)

[Albert556]

ListNode detectCycle(ListNode head) { set<ListNode> seen; ListNode cur = head; while (cur != NULL) { if (seen.find(cur) != seen.end()) return cur; seen.insert(cur); cur = cur->next; } return NULL; }