142. Linked List Cycle II

Description:

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

 

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

'''
[1] C/C++ style - using hashmap)

idea::
1. traversal from head, and store (node.value: node.memory_address). # address is acquired using id(node) in Python
2. check current_node.val exist in hashmap, and compare current_node.address and stored address in hashmap
3-1. if they are same, return it
4. if current_node reach None, there is no cycle in it. so return None

-T/C: O(n)
-S/C: O(n) for hashmap
'''

'''
[2] two pointer)

idea::
* L= length of non cycle part, D=length of cycle part
case 1. there is a cycle in linked list
    1. slow pointer moving to right next node, fast pointer moving to next and next node. both from head
    2. when there is a cycle, it is for sure two pointer will meet at some node.
    3. when they meet, slow pointer has been moved by L+X, fast pointer has been moved by L+X+D.
    4. so, 2(L+X)=L+X+D <=> L+X=D <=> D-X=L
    5. fast pointer will reach at the Node where cycle begins if it move D-X by one from current position(meeting point)
    6. at the same time, if the other pointer move L by one from head will reach at the Node cycle begins.
    7. when fast pointer and the other pointer meet, return that node.
    
cas2. there is no cycle.
    1. follow case1. but, if fast pointer become None. there is no cycle.
    
code::
(below)

-T/C: O(n)
-S/C: O(1)
'''

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow=head
        fast=head
        
        # if fast become None. return None
        while fast!=None:
            
            fast=fast.next
            if fast!=None:
                fast=fast.next
            else:
                return None
            
            slow=slow.next
            
            if fast==slow:
                break
        
        else:   # break checker
            return None
        
        slow=head
        while fast!=slow:
            fast=fast.next
            slow=slow.next
        
        return slow