azl397985856 commented 2 years ago

142. 环形链表 II

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

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

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

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

进阶：

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

yan0327 commented 2 years ago

思路：快慢指针先处理边界条件，若为空，返回nil for fast.Next != nil && fast.Next.Next != nil 慢指针走一步，快指针走两步。当快慢指针相遇，快指针从头开始移动。当快慢指针相等时返回对应指针。如果没有环，for循环结束，直接返回nil

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

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

yetfan commented 2 years ago

思路快慢指针，相遇必有环相遇后加入p指针从头开始，p和slow同时移动，会在入环点相遇

代码

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

        while fast:
            slow = slow.next

            if fast.next:
                fast = fast.next.next
            else:
                return None

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

        return None

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

wxj783428795 commented 2 years ago

思路

用快慢指针，快指针每次走两步，慢指针每次走一步。
当两个指针第一次相遇时，将快指针重置到head。并且快指针从此时开始每次走一步。
当两个指针再次相遇，就是环的入口。

代码

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

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

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

Richard-LYF commented 2 years ago

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: return head

    a= head 
    b= head
    while b and b.next:
        b = b.next.next 
        a = a.next

        if a == b:
            if not b:
                return None
            k = head 

            while k != b:
                k=k.next
                b=b.next
            return b
    return None

Grendelta commented 2 years ago

思路

使用快慢指针，先寻找是否有环，再使用双指针寻找环的起点

代码

class Solution(object): def detectCycle(self, head): """ :type head: ListNode :rtype: ListNode """

    if not head:
        return None

    p = head
    q = head
    while q.next and q.next.next:
        p = p.next
        q = q.next.next
        if p == q:
            p = head
            while p != q:
                p = p.next
                q = q.next
            return p
    return None

复杂度

时间复杂度 O(N)

空间复杂度 O(1)

zjsuper commented 2 years ago

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

ginnydyy commented 2 years ago

Problem

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

Note

Can use set
Or can use two pointers

Solution

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

        Set<ListNode> set = new HashSet<>();
        ListNode ptr = head;
        while(ptr != null){
            if(set.contains(ptr)){
                return ptr;
            }
            set.add(ptr);
            ptr = ptr.next;
        }

        return null;
    }
}

Complexity

T: O(n) n is the number of nodes of the list.
S: O(n) Extra space is required for the set.

wangzehan123 commented 2 years ago

语言支持：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) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            if (fast == slow) {
                break;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}

tian-pengfei commented 2 years ago

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

//        利用快满指针的两次相遇计算出环的大小。然后利用双指针（相差环的大小），从头遍历，计算出相交节点
// 是想操场跑步，如果速度相差两倍的话，他们首次相遇肯定是起点位置，并且是第一次相遇。可以思考成快的要追慢的一圈的距离。
// 他们相遇必定是整数次数，两圈的偶数 指针每次两个。满指针 每次一个 整数
          if(head== nullptr){
              return nullptr;
          }
            ListNode* fastPos = head->next;
          ListNode* slowPos = head;
        while (fastPos!= nullptr&&fastPos->next!= nullptr &&fastPos!=slowPos){

            fastPos = fastPos->next->next;
            slowPos = slowPos->next;

        }
        if(fastPos == nullptr){
            return nullptr;
        }
        if(fastPos->next== nullptr){
            return nullptr;
        }
        int num=0;
        do{
            fastPos = fastPos->next->next;
            slowPos = slowPos->next;
            num++;
        } while (fastPos!=slowPos);
        ListNode* pos1 = head;
        ListNode* pos2 = head;
        for(int i=0;i<num;i++){
            pos2=pos2->next;
        }
        while(pos1!=pos2){
            pos1=pos1->next;
            pos2 = pos2->next;
        }

        return pos1;

    }
};

feifan-bai commented 2 years ago

思路

Slow, fast points with 1 step, 2 steps each time.
If there exists a cycle, fast and slow points will be met at a position.

Find the postion by two points 代码

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

复杂度分析

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

SenDSproject commented 2 years ago

解题思路：使用双指针可以使用O（1）的空间解决，另外一个思路是用set 但是需要额外的储存空间



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

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

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

时间复杂度O（N）
空间复杂度 O（1）

zhy3213 commented 2 years ago

思路

双指针

代码

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

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

Bochengwan commented 2 years ago

思路

同样的可以使用一个set，找到的第一个重复的node则为结果。

代码

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

        return None

复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。
空间复杂度：O(N)

CodeWithIris commented 2 years ago

Note (Fast and slow pointer)

The fast and slow pointers both point to the head node. The fast pointer takes two steps at a time while the slow pointer takes one step at a time. The first traversal determines if the linked list has a circle. If the fast and slow pointers meet, the linked list has a circle, and make the fast pointer point to the head node.
In the second traversal process, both the fast pointer and the slow pointer move one step at atime, and their meeting node is the entry node of the circle in this linked list.

Solution (C++)


class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr) return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        int flag = 0;
        while(fast!=nullptr && fast->next!= nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                flag = 1;
                break;
            }
        }
        if(flag){
            fast = head;
            while(fast != slow){
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
        return nullptr;
    }
};

Complexity

T: O(n): The worst case scenario is to go through the list twice. O(n) + O(n) = O(n)
S: O(1): Use fast and slow pointers' space, so that is O(1)

CoreJa commented 2 years ago

思路

快慢指针navie思路，只领会了快慢指针的表皮，没有深入理解题目第二个难点同样可以快慢指针解决
快慢指针：上述方法改进。假设环形链表公共部分是a，要求的点是ans，快慢指针第一次相遇点是meet，那么起点到ans的路程是a，ans到meet是b，meet到ans是c，而快指针走的路程是慢指针的两倍则有2(a+b)=a+n(b+c)+b，化简得到a+b=n(b+c)，a=n(b+c)-b。如果从起点走到ans (路程为a)就等于从meet点走n圈再回退b步。两个人可以相遇到ans点

代码

class Solution:
    # 快慢指针naive思路，只领会了快慢指针的表皮，没有深入理解题目第二个难点同样可以快慢指针解决
    def detectCycle1(self, head: ListNode) -> ListNode:
        fast = slow = start = ListNode(0)
        start.next = head

        meet = None
        while fast and slow:
            slow = slow.next
            fast = fast.next.next if fast.next else None
            if fast == slow:
                meet = fast
                break

        while meet:
            p, q = start, meet
            while p.next != meet:
                p = p.next
            while q.next != meet:
                q = q.next
            if p != q:
                return meet
            meet = meet.next

        return meet

    # 快慢指针：上述方法改进，假设环形链表公共部分是a，要求的点是ans，快慢指针第一次相遇点是meet，
    # 那么起点到ans的路程是a，ans到meet是b，meet到ans是c，而快指针走的路程是慢指针的两倍
    # 则有2(a+b)=a+n(b+c)+b，化简得到a+b=n(b+c)，a=n(b+c)-b
    # 如果从起点走到ans (路程为a)就等于从meet点走n圈再回退b步。两个人可以相遇到ans点
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = start = ListNode(0)
        start.next = head
        meet = None

        while fast and slow:
            slow = slow.next
            fast = fast.next.next if fast.next else None
            if fast == slow:
                meet = fast
                break

        if not meet:
            return meet
        while (meet := meet.next) != (start := start.next):
            continue
        return meet

xj-yan commented 2 years ago

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head, head
        while fast and 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 None

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

q815101630 commented 2 years ago

快慢指针

Let fast be a pointer moves in the double pace of the slow pointer. Let them start at the same time.

Assume we split the LinkedList into three parts:

A: the part starting from the head to the entry node of the cycle
B: the part that the fast and slow meet (it must be in the cycle if the cycle exists)
C: the part the cycle - B Since fast moves twice speed as slow: A+B+C+B = 2(A+B) Thus, A=C Since right now slow pointer is at the start of C. we can redirect fast to the head and allow fast and slow to move at the same speed by 1 node each time. Then, they will meet at the entry of the cycle.
```
# 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: ''' A + B + C + B = 2(A + B) => A = C => let fast and slow then move in the same pace ''' fast = slow = head if fast and fast.next: fast = fast.next.next else: return None

    slow = slow.next
    while fast != slow:
        if fast and fast.next:
            fast = fast.next.next
        else:
            return None
        slow = slow.next

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

    return fast


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

ZhangNN2018 commented 2 years ago

思路

2倍速快指针与1倍速慢指针。2(a+b)=a+b+c+b
若无环，fast会走到NULL; 若有环，快慢指针终将相遇。
快慢指针相遇的节点到入环的第一个节点的距离c，与从头到入环的第一个节点的距离a相等。

复杂度

时间复杂度: O(N)；
空间复杂度: O(1)。

代码

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 快慢指针相遇的节点到入环的第一个节点的距离，与 从头到入环的第一个节点的距离相等
        fast = head
        slow = head
        while fast and fast.next: #若无环，fast会走到NULL
            fast=fast.next.next
            slow=slow.next
            if fast == slow: #若有环，快慢指针终将相遇
                    temp = head
                    while temp!=slow:
                        slow=slow.next
                        temp=temp.next
                    return temp

falconruo commented 2 years ago

思路: 双指针 fast, slow， fast每次走两步，slow每次走一步如果fast和slow相遇，令fast从头head开始，各走一步，再次相遇时即为环的入口

复杂度分析:

时间复杂度: O(n), n为树的节点数
空间复杂度: 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 NULL;

        ListNode *slow = head, *fast = head;

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

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

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

                return fast;
            }
        }

        return NULL;
    }
};

tongxw commented 2 years ago

思路

龟兔赛跑确认存在环。之后fast指针指向head，fast / slow每次移动一步，再次相遇的地方就是交点。

代码

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

TC: O(n)
SC: O(1)

zwmanman commented 2 years ago

思路

Using a set to track all the node, if it shows again, return that node

代码

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None

        pointer = head
        helper = set()

        while head != None:
            if head in helper:
                return head
            else:
                helper.add(head)
                head = head.next

        return None

复杂度分析

时间复杂度：O(N)，其中 N 为LinkedList长度。
空间复杂度：O(N)

li65943930 commented 2 years ago

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;

Tao-Mao commented 2 years ago

Idea

Fast and slow pointers.

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

    }
}

Complexity

Space: O(1) TIme: O(n)

guangsizhongbin commented 2 years ago

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {

    pos := head;

    // 用一个map记录已经访问过的结点
    visted := map[*ListNode]bool{}

    for  pos != nil {

        // 判断是否存在于map中
        if (visted[pos]){
            return pos;
        } else {
            visted[pos] = true
        }
        pos = pos.Next
    }

    return nil
}

yuetong3yu commented 2 years ago

142. 环形链表 II

没啥好说的。。。做了好多遍。

证明可得：头节点到入口点的距离等于入口点到相交节点的距离。

因此编码：

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

nonevsnull commented 2 years ago

思路

思路与解法
经典的链表环问题，既是题目，也是技巧，别的题目会用到；
做过的题目主要是写法问题，这里有些边界判断，dummy可用可不用；
尽可能做到一次写对，不要有bug；

代码

//with dummy
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;
    }
}

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

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

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

复杂

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

XinnXuu commented 2 years ago

Code（Java）

//1.HashSet
/**
 * 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;
        }
        Set<ListNode> visited = new HashSet<>();
        ListNode pos = head;
        while (pos != null) {
            if (visited.contains(pos)){
                return pos;
            } else {
                visited.add(pos);
                pos = pos.next;
            }
        }
        return null;
    }
}

// 2. Two Pointers
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 (slow == fast) {
                fast = head;
                while (fast != slow) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}

Complexity

Solution 1：

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

Solution 2：

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

ZacheryCao commented 2 years ago

Idea

Two pointers; Fast pointer's speed is twice of the slow one until they meet or the fats one hits the tails. Let's assume it has cycle. The length of cycle is A and the length of acyclic part is B. When fast pointer meets the slow one, the slow one moves B + C and the fast one moves B + C + kA. Here, k is an int. It means the slow one still needs to move A-C to get the intersected node. We have A-C = B + kA, because B + C + kA = 2 * (B + C) which has B = kA-C and (k-1) A is the intersected point. Thus, when we reset the fast point to the head, and let the slow pointer on fast pointer continue moving step by step, they will meet at the intersected pointer.

Code:

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None
        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 fast

Complexity:

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

Yark-yao commented 2 years ago

思路

和昨天的题类似，还是遍历链表，用map记录访问过的节点，当节点再次被访问时，就是环形入口

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    if(head === null){
        return null
    }
    if(head.next === null){
        return null
    }
    const visitMap = new Map()
    let cur = head
    while(cur){
        if(visitMap.get(cur)){
            return cur
        }else{
            visitMap.set(cur,true)
        }
        cur = cur.next
    }
    return null
};

复杂度

时间：O(N) 空间：O(N)

moirobinzhang commented 2 years ago

Code:

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

    cursor_node = head
    while cursor_node is not None:
        if cursor_node in visited:
            return cursor_node
        else:
            visited.add(cursor_node)
            cursor_node = cursor_node.next

    return None

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

hdyhdy commented 2 years ago

方法一：map

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    ans := make(map[*ListNode]bool)
    for head != nil {
        if ans[head] == true{
            return head
        }
        ans[head] = true
        head = head.Next
    }
    return nil
}

时间复杂度为n空间为n 方法2：快慢指针

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slow,fast := head, head
    for fast != nil {
        slow = slow.Next
        if fast.Next == nil {
            return nil
        }
        fast = fast.Next.Next
        if fast == slow {
            pre := head
            for pre != slow {
                pre = pre.Next
                slow = slow.Next
            }
            return pre
        }
    }
    return nil
}

时间为n空间为1

xingzhan0312 commented 2 years ago

/*
 * @lc app=leetcode id=142 lang=javascript
 *
 * [142] Linked List Cycle II
 * 环形链表 2 
 * 解法一： set（）
 * 1. 在空间复杂度为n的情况下，把每一个node都加入到set 里面，遇到的第一个相同的node就是环的入口
 * 2. let data = new Set(), data.has(head) ...
 * 解法二： two pointers
 * 1. 用两种方式来表示fast和slow相遇时，fast走过的路径 得出 L = D
 * 2. 让fast从head开始走L，slow继续走D。再次相遇的时候就是环的入口。
 */

// @lc code=start
/**
 * 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) return null;
    let fast=head;
    let slow=head;

    //when jumping out of this loop, fast and slow are at the same node
    while(fast && fast.next){
        fast=fast.next.next
        slow=slow.next
        //Equal means there is a cycle. 
        if(fast==slow){
            let temp=head;
            while(temp!=slow){
                temp=temp.next;
                slow=slow.next;
            }
            return slow;
        }
    }
    return null;
};
// @lc code=end

1149004121 commented 2 years ago

142. 环形链表 II

思路

要判断是否有环，可以使用快慢指针，快指针走两步，满指针走一步，当有重合时，说明有环。由于是快慢指针，慢指针走的是快指针的1/2，假设环外部分长度为a，从相交节点到相遇结点的长度为b，从相遇结点再走到相交结点的长度为c。则有2（a+b）=a+（n+1）b +n*c，a=c+(n−1)(b+c)。则从head开始慢走，从相交点开始慢走，会在相交结点相遇。

代码


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

复杂度分析

时间复杂度：O(N)，链表长度。
空间复杂度：O(1)。

Husky-Gong commented 2 years ago

Solution

Use fast and slow node to find where they meet - if fast.next == null || fast.next.next == null, it means no meet. Return null
get the meet node, use a curr node starts from head. Move curr and meet step by step, once they meet, the node is the return one.

Code

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

        ListNode fast = head, slow = head;

        ListNode meet = null;

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

            if (fast == slow) {
                meet = slow;
            }
        }

        if (meet == null) {
            return null;
        }

        ListNode curr = head;
        while (curr != meet) {
            curr = curr.next;
            meet = meet.next;
        }

        return meet;
    }
}

Complexity

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

wenlong201807 commented 2 years ago

代码块


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

时间复杂度和空间复杂度

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

shamworld commented 2 years ago

思路

快慢指针

代码

var detectCycle = function(head) {
    if(!head||!head.next) return null;
    let 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;
};

复杂度分析

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

suukii commented 2 years ago

Link to LeetCode Problem

S1: 哈希表

从头开始遍历链表并给每个节点增加一个“已遍历”的标记。
如果在遍历过程中遇到了一个“已遍历”的节点，说明这是环的入口。
但题目不允许修改给定的链表节点，因此可以借用一个额外的哈希表来记录。
注意题目中没有提到节点值是否唯一，仅用节点值作为哈希表的 key 是不够的，需要用节点引用。

/**
 * 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) {
        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;
    }
};

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  const map = new Map();

  while (head) {
    if (map.has(head)) return head;
    map.set(head, true);
    head = head.next;
  }

  return null;
};

Time: $O(N)$，N 为链表长度。
Space: $O(N)$，哈希表的空间。

S2: 双指针

先使用快慢指针来确定链表是否有环。
如果链表有环，那快慢指针相遇的点一定是在环中：
1. 接着把指针 A 移到链表头部，指针 B 留在环内；
2. 指针 A 走一步，指针 B 在环内走一圈；
3. 如果指针 A 和指针 B 相遇了，说明这个节点就是环的入口。

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head

        while slow != None and fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return self.findConnection(head, slow)
        return None

    def findConnection(self, head, loopNode):
        p1 = head
        while True:
            p2 = loopNode
            while p2.next != loopNode and p2.next != p1:
                p2 = p2.next
            if p2.next == p1:
                return p1
            p1 = p1.next

/**
 * 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,
    fast = head;
  // 快慢指针确定有环
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    // 确定有环，开始找环的第一个节点
    if (slow === fast) return findConnection(head, fast);
  }
  return null;

  // ******************************************

  function findConnection(head, loopNode) {
    // p1 走一步，p2 绕环一圈
    let p1 = head;
    while (true) {
      let p2 = loopNode;
      while (p2.next !== loopNode && p2.next !== p1) {
        p2 = p2.next;
      }
      if (p2.next === p1) return p1;
      p1 = p1.next;
    }
  }
};

Time: $O(N*P)$，N 是环外链表的长度，P 是环的长度。
Space: $O(1)$

S3: 双指针+数学证明

先用快慢指针确定链表是否有环，如果是环形链表，快慢指针会在环内的某个节点相遇。

我们分别来看一下两个指针相遇前分别走了多少路程。

快指针

假设走到相遇点之前，快指针在环内走了 n 圈，那快指针走过的总路程可以用S(fast) = a + n(b + c) + b来表示，其中 (b + c) 就是环的长度。

慢指针

因为慢指针在环内走不到 1 圈就会被快指针追赶上，可得慢指针走过的总路程是S(slow) = a + b

而由于快指针的速度是慢指针速度的 2 倍，所以可得以下方程式：

2S(slow) = S(fast) ⇒ 2(a + b) = a + n(b + c) + b

稍微整理一下我们就得到了：

a + b = n(b + c) ⇒ a = (n - 1)(b + c) + (b + c) - b = (n - 1)(b + c) + c

结论就是 a 的长度等于 c 的长度加上 n-1 圈环的长度。

所以如果我们把其中一个指针移动到链表头部，然后让两个指针以相同的速度移动，它们会在环的入口相遇。

ps. 如果 a 很长的话，fast 指针需要在环内走 n - 1 圈再加上 c 的距离，才能和 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;

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

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let fast = head,
    slow = 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;
};

Time: $O(N)$，N 为链表长度。
Space: $O(1)$

Aobasyp commented 2 years ago

思路使用双指针的技巧来完成。

ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = 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;

}

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

ivangin commented 2 years ago

思路

快慢指针

代码

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

复杂度分析

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

Joyce94 commented 2 years ago

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None 
        node = self.isHasCycle(head)
        if node is None:
            return None 
        count = 1 
        fast = node.next
        while fast != node:
            fast = fast.next
            count += 1 
        fast, slow = head, head
        while count:
            fast = fast.next
            count -= 1 
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast

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

tangjy149 commented 2 years ago

思路

快慢指针，分两部分
第一部分：通过快慢指针来判定是否存在环，quick=2*slow，只要能相遇就一定有环，若无环则直接返回null
第二部分：从第一次相遇点开始，再设置q=head，与slow指针同时向后移动，再次相遇则是第一次入环节点
令head到入环节点距离=a，入环节点到第一次相遇点=b，环中剩余部分（第一相遇到入环）=x
a+b=slow 2（a+b）=quick
又quick=a+b+x+b（相当于比slow多走一个环的距离x+b）
解之可得，a=x
故从head从头开始移动和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) {
        if(head==nullptr) return nullptr;
        ListNode *ptr1=head;
        ListNode *ptr2=head;
        bool flag=false;
        while(ptr1->next!=nullptr && ptr1->next->next!=nullptr){
            ptr1=ptr1->next->next;
            ptr2=ptr2->next;
            if(ptr2==ptr1){
                flag=true;
                break;
            }
        }
        if(!flag) return nullptr;
        ListNode *p=head;
        ListNode *q=ptr1;
        while(p!=q){
            p=p->next;
            q=q->next;
        }
        return p;
    }
};

复杂度

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

iambigchen commented 2 years ago

思路

定义快慢指针，快指针的速度是慢指针的两倍。如果他们第一次相遇时，将快指针放到链表的头部，再次相遇的时候，就是环的入口。

关键点

代码

语言支持：JavaScript

JavaScript Code:


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

复杂度分析

令 n 为数组长度。

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

Myleswork commented 2 years ago

思路一

哈希表，遍历一个节点就加入哈希表，如果再次遍历到这个节点说明有，返回即可。

代码

/**
 * 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) {
        unordered_map<ListNode*,int> hash;
        ListNode* cur = head;
        while(cur && hash[cur] == 0){
            hash[cur]++;
            cur = cur->next;
        }
        if(hash[cur] == 1) return cur;
        return NULL;

    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

思路二

快慢指针，若有相等表明有环。但仅仅是有环，还需要再加一个指针去碰环头。这个就有一个证明的过程了，具体可以看leetcode官解

代码

/**
 * 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 NULL;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) break;
        }
        if(slow != fast) return NULL; //说明未成环
        ListNode* cur = head;
        while(cur != slow){
            cur = cur->next;
            slow = slow->next;
        }
        return cur;

    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

EggEggLiu commented 2 years ago

代码

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

复杂度

时间 O(n)

空间 O(1)

herbertpan commented 2 years ago

思路

只能说自己画图看吧

code

public ListNode detectCycle(ListNode head) {
        // corner case
        if (head == null) {
            return null;
        }

        // does it have a cycle?
        ListNode slow = head;
        ListNode fast = head;
        boolean meetEachOther = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                meetEachOther = true;
                break;
            }
        }

        if (!meetEachOther) {
            // while loop exit because fast reaches end
            return null;
        }

        // it has a loop
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

复杂度分析

time: O(N), N is the number of individual listNodes space: O(1)

KennethAlgol commented 2 years ago

思路

快慢指针

语言

java

/**
 * 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 pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while(pos != null){
            if(visited.contains(pos)){
                return pos;
            }else{
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

复杂度分析

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

testeducative commented 2 years ago

思路

快慢指针

代码

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

复杂度

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

732837590 commented 2 years ago

使用双指针 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(slow == fast)
        break;
    }

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

    ListNode p1 = head;
    ListNode p2 = slow;//fast
    while(p1 != p2){
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;

}

}

Toms-BigData commented 2 years ago

【Day 11】142. 环形链表 II

思路

快慢指针

golang代码

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

复杂度

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

L-SUI commented 2 years ago

leetcode-pp / 91alg-6-daily-check

【Day 11 】2021-12-22 - 142. 环形链表 II #18

142. 环形链表 II

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度分析

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

思路

代码

复杂度

Problem

Note

Solution

Complexity

思路

代码

思路

代码

Note (Fast and slow pointer)

Solution (C++)

思路

代码

快慢指针

思路

复杂度

代码

思路

代码

思路

代码

Idea

Code

Complexity

思路

代码

复杂

Code（Java）

Complexity

Idea

Code:

Complexity:

思路

代码

复杂度

142. 环形链表 II

思路

代码

Solution

Code

Complexity

代码块

时间复杂度和空间复杂度

思路

代码

复杂度分析

S1: 哈希表

S2: 双指针

S3: 双指针+数学证明

思路

代码

复杂度分析

思路

代码

复杂度

思路

关键点

代码

思路一

代码

思路二

代码

代码