【Day 11 】2021-09-20 - 142. 环形链表 II

[azl397985856]

142. 环形链表 II

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

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

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

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

进阶：

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

[L-SUI]

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; };

[KennethAlgol]

思路

双指针法,快慢指针

语言

java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        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 (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

[AruSeito]

思路

快慢指针，第一次相遇，把慢指针放到链表头去，然后再一步步走，和快指针相遇了这个地方就是环的起点

var detectCycle = function (head) {
  if (!head || !head.next) return null;
  let slow = head,
    fast = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }

  return null;
};

[yanglr]

思路

方法1: 使用 set

使用set，判断重复出现。当出现环时, 会试图将一个已经插入到set中的node进行第二次插入，此时set会获得状态: 插入失败。 故第一个重复插入(插入的状态为false)的结点就是入环的第一个结点。

代码

实现语言: C++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> st;
        ListNode* p = head;
        ListNode* res = NULL;

        while(p != NULL)
        {
            if(st.insert(p).second == false)  /* 向set中插入node失败，说明是第2次出现了，第1个出现第2次的 */
            {
                res = p;
                return res;
            }
            p = p -> next;
        }
        return NULL;
    }
};

代码已上传到: leetcode-ac/91algo daily - github.com

复杂度分析

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

方法2: 快慢指针

对链表先做一轮遍历, 这一轮中, 快指针每次走2步, 慢指针每次走1步, 如果快慢指针恰好指向了同一个结点就break掉。

如果快慢指针还没相遇就把慢指针拉回链表开头的位置进行第2轮遍历, 这一轮中, 快指针每次走1步, 慢指针每次也走1步, 循环结束时，慢指针即为入环的第一个结点。

代码

实现语言: C++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* 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 (fast != slow)   /* 只要还没相遇就继续循环 */
        {
            slow = slow->next;
            fast = fast->next;  /* 此轮循环每次只走一步 */
        }
        return slow;
    }
};

复杂度分析

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

[BpointA]

思路

单指针，用哈希表辅助查找。如果碰到None则返回None，如果指针指向的结点已经在哈希表中，则返回该结点。

Python3代码

# 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:
        has=set()
        t=head
        while t!=None:
            if t in has:
                return t
            has.add(t)
            t=t.next
        return None

复杂度

时间复杂度:O(n) 遍历一次链表

空间复杂度:O(n) 利用哈希表求解

优化

利用数学推导，可得到通过快慢指针找入口的方法。其本质是，快指针在相遇时已比慢指针多跑了n圈，将快指针移到头部，二者以相同速度移动，就能在入口相遇。遍历了两次链表，但能将空间复杂度缩为 O(1)

# 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=head
        fast=head
        while fast!=None and fast.next!=None:
            fast=fast.next.next
            slow=slow.next
            if fast==slow:
                break
        if fast==None or fast.next==None:
            return None
        fast=head
        while fast!=slow:
            fast=fast.next
            slow=slow.next
        return fast

[cicihou]

# 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:
        cur = head
        cache = {}
        while cur:
            if cur not in cache:
                cache[cur] = cur
            else:
                return cache[cur]
            cur = cur.next
        return None

[joriscai]

思路

• 双指针的方法
• 首先要判断是否链表有环
• 当链表有环时，两个指针会在环内相遇
• 存在环外长度 = 相遇点到入环点长度 + n次环的长度
• 因此，相遇后将另一个指针重新从表头部走，最终将再入环点相遇

  代码

  javascript

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
  let slow = head
  let fast = head

  while (fast && fast.next && fast.next.next) {
    slow = slow.next
    fast = fast.next.next

    // 相遇了
    while (slow === fast) {
      // 相遇点到入环点的距离等于链头到入环点的距离
      slow = head
      while (slow !== fast) {
        slow = slow.next
        fast = fast.next
      }
      return slow
    }
  }
  return null
};

复杂度分析

• 时间复杂度：O(n)，对于慢指针，走a+b到相遇点，后面再走c到入环点，刚好把整个链表走完
• 空间复杂度：O(1)，只用了两个指针空间

[Mahalasu]

思路

快慢指针（讲义）

# 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:
        if not head or not head.next or not head.next.next:
            return None

        slow = head.next
        fast = head.next.next

        while slow != fast:
            if not fast or not fast.next:
                fast = None
            else:
                fast = fast.next.next
            slow = slow.next

        if fast == None:
            return None

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

T: O(N) S: O(1)

[bingyingchu]

Plan:
1) User the two pointer technique, slow/fast pointers
2) P1 starts from head and p2 starts from where slow and fast meet
3) move both p1 and p2 at the same speed, and p1 and p2 meet at the entrance of the cycle

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None

        slow = fast = head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

            if slow == fast:
                p1 = head
                p2 = fast

                while p1 != p2:
                    p1 = p1.next
                    p2 = p2.next
                return p1
        return None

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

[yachtcoder]

Fast and slow pointer, or the Hare and Tortoise algorithm.

1. Fast pointer moves 2 steps a time, slow pointer 1 step a time.
2. If the two meet then there's cycle.
3. Once they meet, move the fast pointer back to the head, then move it 1 step a time.
4. When the two meet again, they meet at the entry of the cycle. Time: O(n) Space: O(1)

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

[ysy0707]

思路：通过快慢指针找到环的入口

public class Solution {
    public ListNode detectCycle(ListNode head) {
        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 (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

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

[banjingking]

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

                while (fast!=null && fast.next!=null){
                    fast = fast.next.next;
                    slow = slow.next;

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

[absent1353]

思路

快慢指针

代码

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

复杂度

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

[alwaysbest]

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; }

[pophy]

思路

• 快慢指针 fast slow 判断是否有环
  • 当 fast == slow时
  • fast重新指向head 同时fast = fast.next slow = slow.next
  • 当fast == slow时 返回fast
  • 如果找不到fast == slow 则没有环

Java Code

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

时间 & 空间

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

[thinkfurther]

思路

fast 以两倍速slow遍历，直到fast==slow.然后fast和head同时前进，直到相等

代码

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

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

            if slow == fast:
                while head != slow:
                    head = head.next
                    slow = slow.next
                return head
        return None

复杂度

时间复杂度 ：O(n)

空间复杂度：O(1)

[zjsuper]

Idea: fast and slow pointers:

1. fast x2 slow x1, if meet, fast = head
2. fast x1 and slow x1, if meet, return node Time: O(n) Space:(1)

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = head
        slow = head 
        if fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        else:
            return None
        while slow != fast and fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            #print(slow.val)
        if fast ==None:
            return None
        elif fast.next == None:
            return None
        fast = head
       # print(fast.val)
        #print(slow.val)
        ans = 0
        while slow != fast:
            slow = slow.next
            fast = fast.next

            ans += 1
        return fast

[xieyj17]

# 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:
        p1 = head
        p2 = head
        while p1 is not None and p1.next is not None:
            p1 = p1.next.next
            p2 = p2.next

            if p1 == p2:
                while True:
                    if p2 == head:
                        return head
                    else:
                        head = head.next
                        p2 = p2.next               

        return 

Space O(1)

Time O(N)

[raoshuang]

思路： 快慢指针+数学公式推导 代码： class Solution { public: ListNode detectCycle(ListNode head) { if(head == nullptr || head->next == nullptr){ return nullptr; } ListNode slow = head; ListNode fast = head; while(fast != nullptr && fast->next != nullptr){ slow = slow->next; fast = fast->next->next; if(slow == fast){ ListNode index1 = head; ListNode index2 = slow; while(index1 != index2){ index1 = index1->next; index2 = index2->next; } return index2; } } return nullptr;
} };

[ivalkshfoeif]

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

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

    }
}

[fzzfgbw]

思路

代码

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

}

复杂度分析

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

[zhiyuanpeng]

class Solution:

    def getIntersect(self, head):
        fast, slow = head, head
        if not head:
            return None
        if not head.next:
            return None

        while fast.next:
            slow = slow.next
            fast = fast.next.next
            if not slow or not fast:
                return None
            if slow == fast:
                return slow
        return None

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

        slow = self.getIntersect(head)
        fast = head
        if slow == None:
            return None
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return fast

time complexity O(n) space complexity O(1)

[zhangzz2015]

思路

• 方法1 使用快慢指针先找到intersec点，如果有intersec点，则表明有环，如果没有则没环，注意要先移动再判断，避免初始设置相同，返回错误。找到intersec点，再移动fast或者slow到head，使用相同速度，则相同点为intersec的第一个点。仔细推导如下。如果有环 环之前的大小为l 环的大小为 m 首先计算第一次快慢指针的相遇点 (l + x)*2 = l + m +x 可知道l = m-x 。如果slow指针回到原点，快指针再走 m - x 慢指针走 l 下，正好达到环的第一个点。时间复杂度为O(N)，空间复杂度为O(1)
• 方法2，可使用hash set，记录走得节点，如果碰到第一个重复点，则是环的第一个点。时间复杂度为O(N)，空间复杂度为O(N)

关键点

代码

• 语言支持：C++

C++ Code:

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

        ListNode* fast = getInterSect(head);
        if(fast==NULL)
            return NULL;

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

    }

  ListNode* getInterSect(ListNode* head)
  {
        ListNode* fast = head; 
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next; 
            slow = slow->next; 
            if(fast == slow)
                return fast; 
        }

        return NULL; 
  }
};

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

        if(head == NULL)
            return NULL; 
        unordered_set<ListNode*> recordNode; 

        while(head)
        {
            if(recordNode.find(head)!=recordNode.end())
                return head; 

            recordNode.insert(head);
            head = head->next;
        }

        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)

方法二：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;

        while (current != null) {
            if (visited.contains(current)) return current;
            visited.add(current);
            current = current.next;
        }
        return null;        
    }
}

复杂度分析

令n为链表长度

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

[comst007]

142. 环形链表 II

---

思路

快慢指针。fast, slow 初始都是指向链表头。每次 fast走两步, slow每次走一步。
如果存在环，因为fast速度是slow的两倍, fast会追赶上slow。如果不存在环，则fast会先走到链表结尾。

如果存在环，slow从链表起点重新走,fast则继续从相遇的结点走，只是每次走一步。当两个指针再次相遇的时候就是环的起始节点。

代码

• C++

/**
 * 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) return head;
        ListNode *fast, *slow;
        fast = head;
        slow = head;
        int start = 1;
        while(fast && (start || fast != slow)){
            if(start == 1) start = 0;
            if(!fast -> next) return NULL;
            fast = fast -> next;
            if(!fast -> next) return NULL;
            fast = fast -> next;

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

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

---

复杂度分析

• 时间复杂度 $O(n)$, n 为链表节点数。
• 空间复杂度 $O(1)$

[Yufanzh]

Intuition

A typical two pointers (slow and fast pointers) problem. first of all, fast pointer goes twice the speed of the slower pointer. If they can eventually meet, then there is circle in the list; if fast pointer reaches to null, there is no circle. Then to find the starting point of the circle. We can re-direct either pointer back to head and then move in the same speed. Then they will meet at the starting point of the circle

Algorithm in python3

# 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 and fast pointers
        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                break
        if not fast or not fast.next:
            return None
        slow = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return slow

Complexity Analysis

• Time complexity: O(N) since we need to traverse through the linked list
• Space complexity: O(1)

[joeytor]

思路

使用快慢指针技巧, 慢指针走一步快指针走两步

这样如果快指针先碰到None, 那么代表没有环

否则快指针会和慢指针在环里相遇, 相遇时再用一个新的指针从head, 慢指针从相遇点都以速度1前进, 再一次相遇点即是环起点

代码

# 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:

        if not head or not head.next:
            return None

        slow, fast = head.next, head.next.next

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

        if not fast or not fast.next:
            return None

        new = head

        while new != slow:
            new = new.next
            slow = slow.next

        return slow

复杂度

时间复杂度: O(n) n 为链表长度, 因为慢指针两次都没有遍历完整个链表, 快指针 走的路第一次是慢指针的 2 倍, 第二次相同, 所以时间复杂度是 O(n)

空间复杂度: O(1) 只用了常数级别空间

[falconruo]

思路: 利用两个指针slow、fast，快(fast)指针走两步，慢(slow)指针走一步。

复杂度分析:

1. 时间复杂度: O(n), n为结点数
2. 空间复杂度: O(1)

代码(C++):

/**
 * 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 || !head->next) return nullptr;

        ListNode *fast = head, *slow = head;

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

            if (fast == slow)
                break;
        }

        if (!fast || !fast->next) return nullptr;

        fast = head;

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

[heyqz]

代码

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                break

        if fast is None or fast.next is None:
            return None

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

        return fast

complexity

time complexity: O(n) space complexity: O(1)

[XinnXuu]

思路

快慢指针，快指针速度为慢指针的两倍。因为经证明链表起点到入环点的距离L等于第一次相遇点到入环点的距离+整数个环长。所以第一次相遇后用另一指针从链表重新以与slow相同速度遍历，这一次的相遇点即为入环点。

代码

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

复杂度分析

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

[laofuWF]

💻Code:

# move slow and fast pointer until they meet
# put fast back to head and move 1 step along with slow pointer 
# the meeting point is the res
# time: O(N)
# space: O(1)
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head: return head
        if not head.next: return None

        slow = fast = head
        res = None

        while fast and fast.next: 
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                res = fast
                break;

        if not res: return None

        slow = head
        while slow != res:
            slow = slow.next
            res = res.next

        return res

[Daniel-Zheng]

思路1

Hashset判断是否有重复节点。

代码(C++)

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)

思路2

双指针，一个Fast，一个Slow。两者在环内第一次相遇后，Slow到环入口的距离就等于Head到环入口的距离。

代码(C++)

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

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

复杂度分析

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

[siyuelee]

1. hash map

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        seen = dict()
        while head:
            if head in seen:
                return head
            else:
                seen[head] = 1
            head = head.next
        return head

time complexity: O(n) space: O(n)

2. two pointers

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """      
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow: break
        if not fast or not fast.next:
            return None

        new = head
        while new != slow:
            slow = slow.next
            new = new.next
        return slow

time complexity: O(n) space: O(1)

[mmboxmm]

思路

数学题，知之为知之不知为不知。可是有些公司就是要考这些记忆的题目。

代码

public 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 (fast == slow) break;
        }

        if (fast == null || fast.next == null) return null;

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

复杂度

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

[BlueRui]

Problem 142. Linked List Cycle II

Algorithm

• We will use a two pointers, a slow one and a fast one to traverse from the head. Slow pointer moves one node per steps, and fast pointer moves two nodes per step.
• If there is a cycle, the fast pointer will catch up with the slow one. Otherwise, the fast one will reach null.
• When the fast pointer catches up with the slow one, move the fast one to head. Then both pointers moves one node per step until they reach the same node which is the beginning of the cycle.

Complexity

• Time Complexity: O(N), where N is the total number of nodes.
• Space Complexity: O(1)

Code

Language: Java

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    ListNode fast = head, 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;
    }

[chen445]

思路

Solution 1: We have a set to keep track the node that we have visited. If the node is in the visited, this means we have found the cycle entry.

Solution 2: We have two pointers slow and fast.Slow moves one at the time, and fast moves two at the time. If they meet, this means we have cycle. We start moving head and slow one at the time, until they meet. The meet point is the entry of the cycle.

代码

Solution 1

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

Solution 2

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow=fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                while head:
                    if slow==head:
                        return head    
                    head=head.next
                    slow=slow.next
        return None

复杂度

Solution 1

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

Solution 2

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

[jz1433]

思路

2 pointers, slow and fast

代码

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next: 
            return None
        fast, slow = head, head
        while True:
            if not fast or not 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 fast

复杂度

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

[james20141606]

Day 11 142. Linked List Cycle II (linked list, two pointers)

• Problem Link

  • 142. Linked List Cycle II

• Ideas

  • Similar to yesterday's problem. A naive solution is to use hash table to store the nodes in A. Then if we find a node in B is contained in set A we could return the node. Complexity: Time: O(N), Space: O(N)
  • O(1) space solution. The tricky part is we could use two pointers, starting from head, the fast pointer travel two nodes/step, the slow pointers travels one node/step. We let the distance before entering the loop to be L,Then when the pointers meet for the first time, we define the distance the slow pointer travels in the loop to be C, and the remaining distance to be D. Then we move the fast pointer to head and set the speed to be one node/step. The second time they meet is the loop entrance. Proof: L+C+D+C = 2(L+C) --> L =D. And then when the fast pointer starts from head for the second time and travels L nodes, the slow pointer will travel D nodes and since L=D so they meet. Note that we use another X var to deal with the list with zero/one node. Complexity: Time: O(N), Space: O(1)

• Complexity:

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

• Code

#naive solution
def detectCycle(self, head: ListNode) -> ListNode:
    seen = set()
    A = head
    while A:
        if A in seen:
            return A
        seen.add(A)
        A = A.next

#two pointer solution
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        ptA = head 
        ptB = head 
        X = None
        while ptA and ptA.next:
            ptA = ptA.next.next
            ptB = ptB.next
            if ptA ==ptB:
                X = ptA
                break
        if not X:
            return None  #if ptA or ptA.next is None, X will still be None, so return None
        ptA = head
        while ptA !=ptB:
            ptA = ptA.next
            ptB = ptB.next
        return ptA

• other resources:

[HackBL]

• 快慢指针

  public class Solution {
  public ListNode detectCycle(ListNode head) {
      if (head == null) return null;
      ListNode fast = head, slow = head;
  
      while (fast.next != null && fast.next.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;
  }
  }

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

[biancaone]

09/19/2021 142. 环形链表 II 题目链接

思路 🏷️

需要理解以后背答案的题。

---

代码 📜

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None

        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

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

                return fast

        return None

---

复杂度 📦

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

  ---

[bolunzhang2021]

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

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

[Menglin-l]

思路：

1.还是用快慢指针来解，快指针一次走两步，慢指针一次走一步。如果相遇，说明有环；如果快指针指向了null，说明没环。

2.相遇并不能确定环起点的位置，因为它们会在环内相遇。

3.从相遇位置找环起点用到了另一个临时指针，具体过程需要画图。

---

代码部分：

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

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            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 null;
    }
}

---

复杂度：

Time: O(N)

Space: O(1)

[chakochako]

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None

        fast = head
        slow = head

        while True:
            if not (fast and fast.next):
                return None
            else:
                fast = fast.next.next
                slow = slow.next
            if fast == slow:
                break

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

[zol013]

思路：启动两个指针， 快指针一次移动两格，慢指针一次移动一格。 当他们相遇的时候重置快指针到head并且一次前进一格，再次相遇时即是环的起点 Python 3 Code:

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

Time Complexity: O(N) Space Complexity: O(1)

[qyw-wqy]

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) break;
        }
        if (fast == null || fast.next == null) return null;

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

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

[nonevsnull]

思路

• 拿到题的直觉解法

经典的双指针跑圈问题；

- 建dummy node
- fast,slow双指针同时从dummy出发
- 如果到头了，return null
- 如果相遇了，slow指针不动，fast指针回dummy
- fast，slow再次同时从当前位置出发，且都以慢速前进
- 再次相遇地即为环的起点

影响bug-free的地方

- dummy要有，减少边界判断
- 第一次跑圈的条件，slow == fast不能放在while(如果都从dummy出发)，也不能放在开头，要放在结尾，避免逻辑错误；
- dummy虽然能覆盖边界，但还是要自我检测，不然有时候有些边界会漏掉

AC

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode fast = dummy;
        ListNode slow = dummy;

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

        if(slow == null || fast == null || fast.next == null) return null;

        fast = dummy;

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

        return slow;
    }
}

复杂

time: O(N) space: O(1)

[lilixikun]

思路

双指针、利用快慢指针先让它们相交、然后再重置头节点、再次相遇就是交点

代码

var detectCycle = function(head) {
    if(!head||!head.next)return null
    let fast = slow =head
    while(fast && fast.next){
        fast = fast.next.next
        slow = slow.next
        // 相遇
        if(slow==fast){
            slow = head
            while(slow!==fast){
                slow = slow.next
                fast = fast.next
            }
            return slow
        }
    }
    return null
};

复杂度

• 时间复杂度：O（n）
• 空间复杂度：O（1）

[florenzliu]

Explanation

• Use two pointers: fast and slow
  • fast pointer takes 2 steps each time
  • slow pointer takes 1 step each time
• If there is no cycle in the linked list, fast pointer will stop at None
• If there is a cycle in the linked list, fast and slow pointer will eventually point to the same node.
  • when the two pointers meet at some node, break the loop.
  • the length not in the cycle (L), the length of the cycle (C), the length from the intersection to the meeting node (a)
  • fast: L + n * C + a
  • slow: L + a
  • n >= 1, fast = 2 * slow
  • F + a = nC
• Place the fast pointer to the head and move the fast and slow pointers 1 step at a time.
• The first point where the fast and slow pointers meet will be the starting point of the cycle.

Python

# 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:
        fast, slow = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break

        if not fast or not fast.next:
            return None

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

        return slow

Complexity

• Time Complexity: O(N) where N is the size of the linked list
• Space Complexity: O(1)

[tongxw]

思路

快慢指针法（需要证明）或者把所有节点放到哈希表里

代码

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

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

  return fast;
};

TC: O(len(head) SC: O(1)

[ai2095]

LC142. Linked List Cycle II

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

Topics

• Linked List

Similar Questions

Medium

• https://leetcode.com/problems/design-phone-directory/
• https://leetcode.com/problems/swap-adjacent-in-lr-string/
• https://leetcode.com/problems/subdomain-visit-count/

思路

Two pointers.

1. Use two pointers (one moving one step each time and one moving two steps each time) to check whether there is cycle.
2. Once a cycle is found, use two pointers to find the beginning of the cycle.

代码 Python

# 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:
        # Border case
        if not head or not head.next:
            return None

        # Two pointers
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                break

        # Fast reaches the end and there is no cycle
        if not fast.next or not fast.next.next:
            return None

        # Try to find the beginning of the cycle
        result = head
        while result != slow:
            result, slow = result.next, slow.next

        return result

复杂度分析

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