azl397985856 commented 1 year ago

142. 环形链表 II

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

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

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

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

进阶：

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

bookyue commented 1 year ago

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

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

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

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

        return fast;
    }

JiangyanLiNEU commented 1 year ago

Two pointers
Time = O(n)

Space = O(1)

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

954545647 commented 1 year ago

思路

哈希法：遍历链表，将每个值都保存到 hash 表中，如果存在重复则该节点是入口节点

代码

/**
 * 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 || !head.next) return null;
  let arr = new Set();
  while (head) {
    if (arr.has(head)) return head;
    arr.add(head);
    head = head.next;
  }
  return null;
};

复杂度分析

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

kofzhang commented 1 year ago

思路

快慢指针，快指针两步，慢指针一步。如果走完不相遇，就返回None 如果相遇，slow从头再走，都是一步一步走，直到相遇，即为所求。

复杂度

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

代码

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

csthaha commented 1 year ago

复杂度：

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

代码：

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    const visited = new Set();
    let res = null,
        cur = head;
    while(cur) {
        if(!visited.has(cur)) {
            visited.add(cur)
            cur = cur.next;
        } else {
            res = cur;
            break;
        }
    }

    return res;
};

airwalkers commented 1 year ago

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

joriscai commented 1 year ago

思路

双指针的方法
首先要判断是否链表有环
当链表有环时，两个指针会在环内相遇
2(L+C) = L + 2C + D
因此，相遇后将另一个指针重新从表头部走，最终将再入环点相遇
代码

javascript

/**
 * 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 || !head.next) return null
    let slow = head
    let fast = head
    while (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)，只用了两个指针空间

Size-of commented 1 year ago

/**

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

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

if (quick === slow) { quick = head break } }

if (!quick || !quick.next) return null

while (quick !== slow) { quick = quick.next slow = slow.next }

return quick };

NorthSeacoder commented 1 year ago

快慢指针

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if (!head || !head.next) return null;
    //循环时需要 fast 跟 slow 不相等,所以先走一步
    let fast = head.next.next;
    let slow = head.next;
    while (slow != fast && fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    //没有环
    if (slow != fast) return null;
    let point = head;
    //从相遇点到入环点和从 head 到相遇点节点数相同
    while (point !== slow) {
        point = point.next;
        slow = slow.next;
    }
    return slow;
};

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

哈希表

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    //至少 3 个节点才能成环
    if (!head || !head.next) return null;
    const set = new Set();
    let point = head;
    while (point) {
        if (set.has(point)) return point;
        set.add(point);
        point = point.next;
    }
    return null;
};

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

chanceyliu commented 1 year ago

代码

export 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 {
  const visited = new Set();
  while (head !== null) {
    if (visited.has(head)) {
      return head;
    }
    visited.add(head);
    head = head.next;
  }
  return null;
}

复杂度分析

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

FlipN9 commented 1 year ago

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

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

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

Elsa-zhang commented 1 year ago

# 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]:
        flag = False
        node1, node2 = head, head
        while node2 and node2.next:
            node2 = node2.next.next
            node1 = node1.next
            if node1 == node2:
                flag = True
                break

        if not flag:
            return None

        node2 = head
        while node2!=node1:
            node2 = node2.next
            node1 = node1.next
        return node2

Meisgithub commented 1 year ago

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

RestlessBreeze commented 1 year ago

code

/**
 * 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 *s = head;
        ListNode *f = head;
        while (f && f -> next)
        {
            s = s -> next;
            f = f -> next -> next;
            if (s == f) break;
        }
        if (!f || !f -> next) return nullptr;
        f = head;
        while (f != s)
        {
            s = s -> next;
            f = f -> next;
        }
        return s;
    }
};

harperz24 commented 1 year ago

hashing

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

    node_set = set()
    cur = head

    while cur:
        if cur in node_set:
            return cur
        node_set.add(cur)
        cur = cur.next

    return None

    # hashing
    # time: O(n)
    # space: O(n)

Floyd's cycle-finding

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

    fast = head
    slow = head

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

        if slow == fast:
            # reset slow to head and keep fast at the point where they met
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow

    return None

    # Floyd's cycle-finding algorithm
    # time: O(n)
    # space: O(1)

wangqianqian202301 commented 1 year ago

思路

使用快慢指针判断是否有环从第一次相遇处断开，分两路再往下走，如果一个指针到头，换到另一路，直到相遇

代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None        
        oneStep = head
        twoStep = head.next
        while oneStep is not None and twoStep is not None:
            if oneStep == twoStep:
                twoStep = oneStep.next
                oldHead = head
                newHead = twoStep
                oneStep.next = None
                while head != twoStep:
                    head = head.next
                    twoStep = twoStep.next
                    if head is None:
                        head = newHead
                    if twoStep is None:
                        twoStep = oldHead
                return head
            oneStep = oneStep.next
            twoStep = twoStep.next
            if twoStep is not None:
                twoStep = twoStep.next
            else:
                break
        return None

复杂度

O(n) O(1)

Leonalhq commented 1 year ago

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

kyo-tom commented 1 year ago

思路

使用双指针的方法。分别定义两个指针，一个指针为慢指针，步长为 1，另外一个指针为快指针，步长为 2。

两个指针一起从链表头节点 head 出发.

如果链表不存在环，则快指针会先到达链表尾节点，判断是否为尾节点的依据是指针 next 是否为空。

如果链表存在环的话，快慢指针进入环后会一直在环内循环。

由于快指针步长比慢指针大 1，因此在环内快指针最终会追上慢指针，判断追上慢指针的条件就是快指针指向的地址等于慢指针指向的地址。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode quikly = head;
        while(quikly!= null && quikly.next != null) {
            slow = slow.next;
            quikly = quikly.next.next;
            if (slow == quikly) {
                return true;
            }
        }
        return false;
    }
}

复杂度分析

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

jmaStella commented 1 year ago

思路

快慢指针+数学

代码

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

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

复杂度

时间 O(N) 空间 O(1)

Fuku-L commented 1 year ago

思路

快慢指针

每次 p1 走一步，p2 走两步。如果存在环，那么 p2 走了n圈之后会和p1在环中的某个节点相遇。
把 p1 环中，p2 指向头节点。p1 和 p2 每次都走一步，最终p1和p2会在环的入口相遇。

代码

以下代码包括测试验证。

public class Q0142LinkedListCycleIi {
    public static void main(String[] args) {
        Solution solution = new Q0142LinkedListCycleIi().new Solution();
        int[] arr = new int[]{-21, 10, 17, 8, 4, 26, 5, 35, 33, -7, -16, 27, -12, 6, 29, -12, 5, 9, 20, 14, 14, 2, 13, -24, 21, 23, -21, 5};
        int cy = 24;
        ListNode head = new Q0142LinkedListCycleIi().new ListNode(arr[0]);
        ListNode cur = head;
        ListNode temp = null;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new Q0142LinkedListCycleIi().new ListNode(arr[i]);
            if (i == cy - 1) {
                temp = cur;
            }
            cur = cur.next;
        }
        cur.next = temp;

        ListNode res = solution.detectCycle(head);
        System.out.println(res.toString() + "---" + temp.toString());
        System.out.println(res.equals(temp));
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode p1 = head, p2 = head;
            while (true) {
                if (p2 == null || p2.next == null) {
                    return null;
                }
                p1 = p1.next;
                p2 = p2.next.next;
                if (p1 == p2) {
                    break;
                }
            }
            p2 = head;
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
    }
}

复杂度分析

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

hshen202108 commented 1 year ago

思路

快慢指针起始使用slow和fast作为快慢指针（slow每次走一步，fast每次走两步），起始均为head。若fast顺利走到结尾，说明链表无环，直接返回null；

若两者成功相遇，说明链表有环。我们定义链表起点到环入口距离为x，环内节点数量为y。那么从链表起点到环入口的任意路径都能归纳成x+k * y（其中k>=0）。

当两者首次相遇时，假设slow走的距离为d1，而fast走的距离为d2，根据速度的差定义可知d2=d1 2。同时根据「141.环形链表」结论，两者必然在环中相遇，并且一定是fast在环内从后面追上slow，因此d2相比于d1必然是多走了y的整数倍，即有d2=d1+m y（其中m为圈数），即可推导出d1=m * y。

同时根据链表起点到环入口的任意路径均表示为x+k * y，我们知道如果 slow再走x步会到达环入口，同时链表起点到环入口也是x步，因此我们可以复用fast，将其复位到链表起点，和slow一起每次往前一步，当两者再次相遇，必然是同时位于环口。

public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        boolean flag = false;
        while (!flag && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) flag = true;
        }
        if (!flag) return null;
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

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

KrabbeJing commented 1 year ago

思路

哈希表

代码

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

空间复杂度O（N）

思路2

快慢指针

代码

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

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

空间复杂度O（1）

ZhuMengCheng commented 1 year ago

 给每个节点记录下来,如果相同则有环

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let map = new Map();
    while (head !== null) {
        if (map.has(head)) {
            return head;
        }
        map.set(head);
        head = head.next;
    }
    return null;

};

复杂度分析

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

Zoeyzyzyzy commented 1 year ago

/*
 * suppose length of linklist is a + b (b is circle's length),
 * when fast & slow meet the fast's distance: f = 2 * s , f = s + nb
 * (相遇时a比b多走了nb)
 * => s = nb , f = 2nb; start from head, if we want to find the start of the
 * circle,
 * we should have k = a + nb, at this time, s alreay get nb, it needs another a;
 * there is a new pointer start from head, this pointer will meet slow at the
 * start of circle,
 * which will take a steps;
 * time complexity: O(n), space complexity: 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) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

yingchehu commented 1 year ago

思路

快慢指針，快指針走兩步，慢指針走一步當兩個指針重疊的時候，代表快指針超越慢指針剛好一圈的距離快指針距離 = 2 * 慢指針距離快指針距離 - 慢指針距離 = 環圓周長 => 慢指針距離 = 環圓周長這時候一個指針原地，另一個指針從頭，等速移動，第一次碰到的就是環開始的節點

Code

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

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

複雜度

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

Horace7 commented 1 year ago

var detectCycle = function(head) {
  // 快慢指针初始化指向 head
  let slow = head;
  let fast = head;
  // 快指针走到末尾时停止
  while (fast && fast.next) {
    // 慢指针走一步，快指针走两步
    slow = slow.next;
    fast = fast.next.next;
    // 快慢指针相遇，说明含有环
    if (slow == fast) {
      // 任一一节点指向头节点
      fast = head;
      // 同步向前进
      while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
      }
      // 返回入口节点
      return fast;
    }
  }
  return null;

Hughlin07 commented 1 year ago

public class Solution {

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

}

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

sye9286 commented 1 year ago

思路

试着理解了一下题解的双指针解法。如果链表存在环，则快指针最后肯定会转一圈和慢指针相遇。

代码


/**
 * 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(N)
空间复杂度：O(1)

JasonQiu commented 1 year ago

The fast pointer is 1x more faster than the slow pointer
If the fast pointer reaches the end without joining the slow pointer, there is no ring in the linked list

If two pointer joins, reset the slow one to the head of the linked list. The two pointers will now move at the same pace and the next joining point will be the start of the ring

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

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

liuxiner commented 1 year ago

var detectCycle = function(head) {
    if(!head) return null;
    let fast = head;
    let slow = head;
    while(fast) {
        console.log('-',fast.val, slow.val)
        slow = slow.next;
        if(!fast.next) return null;
        if(!fast.next.next) return null;
        fast = fast.next.next;
        console.log(fast.val, slow.val)
        if(fast === slow) {
            let test = head;
            while(test !== slow) {
                test = test.next;
                slow = slow.next;
            }
            return test
        }
    }
};

思路：

双指针+计算入环节点公式 a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

复杂度

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

huizsh commented 1 year ago


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

zhangjiahuan17 commented 1 year ago

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

    while True:
        if not (fast and fast.next): 
            return None
        fast = fast.next.next
        slow1 = slow1.next

        if fast == slow1:
            break
    while slow1 != slow2:
        slow2 = slow2.next
        slow1 = slow1.next
    return slow2

Elon-Lau commented 1 year ago

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

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

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

    return fast;
}

kangliqi1 commented 1 year ago

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

}

liuajingliu commented 1 year ago

解题思路

从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)

FireHaoSky commented 1 year ago

思路：

""" 用两个指针，一个走两步，一个走一步，当相遇时，即为有环，否则返回空；此时慢指针步数为整数倍的环周期；再用一个指针，从头走，慢指针同时向前走，当两个指针相遇时，其位置即为环节点入口位置 """

解题：python

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

复杂度分析：

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

zpbc007 commented 1 year ago

思路

slow 指针移动 S，fast 指针移动 F，则有 F = 2S (快节点移动的距离是慢节点的2倍)
非环长度为 a，环长度为 b，二者相遇时，F - S = n*b (套圈了)
因此 2S - S = n b => S = n b (慢节点移动的总距离是环的长度的 n 倍)
入口节点位置：a + nb
只要 slow 指针再移动 a 即可到达入口

代码

function detectCycle(head: ListNode | null): ListNode | null {
    if (!head) {
        return null
    }    

    let slow: ListNode | null = head
    let fast:  ListNode | null = head

    while(fast !== null) {
        slow = slow?.next  || null
        fast = fast?.next?.next || null

        /**
         * 快慢节点相遇
         */
        if (slow === fast && fast !== null) {
            fast = head
            while (slow !== fast) {
                fast = fast!.next
                slow = slow!.next
            }

            return slow
        }
    }

    return null
};

复杂度

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

Jetery commented 1 year ago


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

AstrKing commented 1 year ago

思路

1、遍历整个链表,同时将每个节点都插入哈希表。由于题目没有限定每个节点的值均不同，因此我们必须将节点的引用作为哈希表的键
2、如果当前节点在哈希表中不存在,继续遍历；如果存在,那么当前节点就是环的入口节点。

代码

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(n)

wangzh0114 commented 1 year ago

思路

快慢指针

代码

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

复杂度分析

TC:O(N)
SC:O(1)

jiujingxukong commented 1 year ago

解题思路

方法一哈希表法

将遍历链表节点，存入哈希表中。如果正在遍历的节点已经存在于哈希表中，那么就存在环，且第一次满足条件的节点就是链表开始入环的第一个节点。

方法二双指针法

具体算法：

定义一个 fast 指针,每次前进两步,一个 slow 指针,每次前进一步
当两个指针相遇时，将 fast 指针重定位到链表头部,同时 fast 指针每次只前进一步
slow 指针继续前进,每次前进一步
当两个指针再次相遇时,当前节点就是环的入口

证明：以下节点数称为距离

x 表示第一次相遇点
L 是起点到环的入口点的距离
C 是环的入口点到第一次相遇点的距离
D 是环的周长减去 C

第一次快慢指针相遇时，慢指针走过的距离为L+m(C+D)+C，快指针走过的距离为L+n(C+D)+C。又因为快指针总共走过的距离是慢指针总共走过的距离的两倍。所以快指针增加一倍的L+C距离所以在两者第一次相遇后将快指针放回开头，两个指针都每次移动一步直到相遇，快指针两次总共走过的距离为2L+p(C+D)+2C，慢指针总共走过的距离为L+q*(C+D)+C。（直觉中这么解释是对的，但是数学不好真不行）

解题代码

方法一哈希表法

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let data = new Set();
  while (head) {
    if (!data.has(head)) {
      data.add(head);
      head = head.next;
    } else {
      return head;
    }
  }
  return null;

};

方法二双指针法

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  if (!head || !head.next) return null;
  let fast = (slow = head);
  do {
//因为fast和fast.next可能在变化过程中变成null,所以要用if判断，确保fast !== null && fast.next !== null才执行里面的代码
    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.next;
    slow = slow.next;
  }
  return fast;
};

复杂度分析

方法一哈希表法

时间复杂度：O（N）遍历链表一遍空间复杂度：O（N）增加存储节点的哈希表

方法二双指针法

时间复杂度：O（N）一直在循环链表空间复杂度：O（1）

joemonkeylee commented 1 year ago

思路

用开辟空间的写出来了快慢指针步长1 2 不等这个方式没做过没写出来记录一种好理解的

代码


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

        while (fast != null)
        {
            slow = slow.next;
            if (fast.next == null) return null;//快指针当前节点和next节点都不为null，才可以走两步
            fast = fast.next.next;
            if (slow == fast)//有环
            {
                while (temp != slow)//找入环节点
                {
                    temp = temp.next;
                    slow = slow.next;
                }
                return temp;   
            }
        }
        return null;
    }

复杂度分析

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

xiaoq777 commented 1 year ago

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

lp1506947671 commented 1 year ago

思路

双指针第一次相遇：设两指针 fast，slow 指向链表头部 head，fast 每轮走 2步，slow 每轮走 1步；

第一种结果： fast 指针走过链表末端，说明链表无环，直接返回 null；

TIPS: 若有环，两指针一定会相遇。因为每走 1 轮，fast 与 slow 的间距 +1，fast 终会追上 slow；第二种结果：当fast == slow时，两指针在环中第一次相遇。下面分析此时fast 与 slow走过的步数关系：

设链表共有 a+b 个节点，其中链表头部到链表入口有 a 个节点（不计链表入口节点），链表环有 b 个节点（这里需要注意，a 和 b是未知数，例如图解上链表 a=4 ,b=5）；设两指针分别走了 f，s 步，则有： fast 走的步数是slow步数的 2 倍，即 sf=2s；（解析： fast 每轮走 2 步） fast 比 slow多走了 n 个环的长度，即f=s+nb；（解析：双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走环的长度整数倍）；以上两式相减得：f=2nb，s=nb，即fast和slow 指针分别走了2n，n 个环的周长（注意： n是未知数，不同链表的情况不同）。

代码

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(1)

linlizzz commented 1 year ago

思路

设定point_1和point_2分别每次走1步和2步，若相遇则有循环，若走到None则无循环

2.相遇后，再走到相遇的步数则为环的长度

3.重新从头开始point_2每次走1步，走掉环的长度后，point_1从头和point_2继续同时开始走每次走1步，走到相遇则为环的起点。

代码

# 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]:
        point_1 = head
        point_2 = head
        l = 0
        while point_2 and point_2.next:
            point_1 = point_1.next
            point_2 = point_2.next.next
            if point_1 == point_2:
                break
        if not point_2 or not point_2.next:
            return None
        while True:
            point_1 = point_1.next
            point_2 = point_2.next.next
            l += 1
            if point_1 == point_2:
                break
        point_1 = head
        point_2 = head
        for i in range(l):
            point_2 = point_2.next
        while point_1 != point_2:
            point_1 = point_1.next
            point_2 = point_2.next
        return point_1

复杂度分析

T(n) = O(n)

S(n) = O(1)

DrinkMorekaik commented 1 year ago

快慢指针

var detectCycle = function (head) {
    let slow = head, fast = head
    while (fast && fast.next) {
        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
};

bingzxy commented 1 year ago

思路

快慢指针，如果不存在环，则快指针必定先指向 NULL，否则，快慢指针必定相交。

代码

/**
 * 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 slow = head, fast = head;

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

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

复杂度分析

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

munmust commented 1 year ago

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

luckyoneday commented 1 year ago

代码

var detectCycle = function(head) {
    let slow = 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
};

snmyj commented 1 year ago

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

        } 
        return nullptr;       
    }
};

tc:o(n); sc:O(n);

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

【Day 11 】2023-02-24 - 142. 环形链表 II #14

142. 环形链表 II

入选理由

题目地址

前置知识

题目描述

思路

代码

思路

复杂度

代码

复杂度：

代码：

思路

代码

复杂度分析

快慢指针

哈希表

代码

code

思路

代码

复杂度

思路

代码

思路

代码

复杂度

思路

代码

思路

思路

代码

思路2

代码

思路

Code

複雜度

思路

代码

思路：

复杂度

解题思路

代码实现

复杂度分析

思路：

解题：python

复杂度分析：

思路

代码

复杂度

思路

代码

复杂度分析

思路

快慢指针

代码

复杂度分析

解题思路

方法一 哈希表法

方法二 双指针法

解题代码

方法一 哈希表法

方法二 双指针法

复杂度分析

方法一 哈希表法

方法二 双指针法

思路

代码

思路

代码

复杂度

思路

代码

复杂度分析

快慢指针

思路

代码

复杂度分析

方法一哈希表法

方法二双指针法

方法一哈希表法

方法二双指针法

方法一哈希表法

方法二双指针法