_142. Linked List Cycle II.md

142. Linked List Cycle II

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 26, 2024

Last updated : June 26, 2024

---

Related Topics : Hash Table, Linked List, Two Pointers

Acceptance Rate : 52.88 %

---

Solutions

• m142 v1 O(1) space.py
• m142 v2 O(n) runtime.py
• m142 v3 O(1) space O(n) runtime.py

Python

m142 v1 O(1) space.py

# 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]:
        if not head :
            return None
            
        currFast = head
        currSlow = head

        loop: bool = False
        while currFast.next and currFast.next.next :
            currFast = currFast.next.next
            currSlow = currSlow.next

            if currFast == currSlow :
                loop = True
                break

        if not loop :
            return None

        loopSize = 1
        currFast = currFast.next
        while currFast != currSlow :
            loopSize += 1
            currFast = currFast.next
        
        currRef = head
        while True :
            for i in range(loopSize) :
                currFast = currFast.next
                if currFast == currRef :
                    return currRef
            currRef = currRef.next

m142 v2 O(n) runtime.py

# 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]:
        if not head :
            return None
        
        past = set()

        while head :
            if head in past :
                return head
            
            past.add(head)
            head = head.next
        return None

m142 v3 O(1) space O(n) runtime.py

# 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]:
        if not head :
            return None
            
        currFast = head
        currSlow = head

        while currFast.next and currFast.next.next :
            currFast = currFast.next.next
            currSlow = currSlow.next

            if currFast == currSlow : # Loop found
                currSlow = head
                while currSlow != currFast :
                    currSlow = currSlow.next
                    currFast = currFast.next

                return currSlow
        return None