160. Intersection of Two Linked Lists

Description:

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

 

'''
[1] brute force)

idea::
read1=from head1 to end and read2=from head2 to end using nested loop
find where read1==read2

code::

read1=headA
while read1!=None:
    read2=headB
    while read2!=None:
        if read1==read2:
            return read1
        read2=read2.next
    read1.read1.next
return None

-T/C: O(m*n), m==len(listA), n==len(listB)
-S/C: O(1)
'''

'''
[2] using length of linked list)

idea::
len(listA) = lenA+d, d is the length of same part with listB
len(listB) = lenB+d
then, diff=len(listA)-len(listB) = lenA-lenB
    if diff>0, lenA is greater than lenB, elif diff<0, lenB>lenA, else lenA==lenB
using this idea, read1(or read2) advance by the diff

ex.
    4 - 1 - 8 - 4 - 5               4 - 1 - 8 - 4 - 5
    |                       =>      |                      
5 - 6 - 1 - 8 - 4 - 5           5 - 6 - 1 - 8 - 4 - 5
|                                   |       (diff==1)  
 => then, traversal two pointer at the same time, if two pointer are same then, return read1(or read2)
 => if there is no intersected point return None
 

code::
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        len_a=0
        cur=headA
        while cur!=None:
            len_a+=1
            cur=cur.next

        len_b=0
        cur=headB
        while cur!=None:
            len_b+=1
            cur=cur.next
            
        
        read1=headA
        read2=headB
        if len_a>len_b:
            for i in range(len_a-len_b):
                read1=read1.next
        elif len_a<len_b:
            for i in range(len_b-len_a):
                read2=read2.next
                
        while read1!=None and read2!=None:
            if read1==read2:
                return read1
            read1=read1.next
            read2=read2.next
        
        return None
        
-T/C: O(lenA + lenB) # maximum is two pass
-S/C: O(1)
'''

'''
[3] circular linked list)

idea::
read1 start at headA and read2 start at headB
they both move one by one. if either one reach at None, the pointer move another' head
ex.
    4 - 1 - 8 - 4 - 5               4 - 1 - 8 - 4 - 5               4 - 1 - 8 - 4 - 5
    |                       =>                      |      =>
5 - 6 - 1 - 8 - 4 - 5           5 - 6 - 1 - 8 - 4 - 5           5 - 6 - 1 - 8 - 4 - 5   
|                                               |               |(r1)               |(r2)


        4 - 1 - 8 - 4 - 5         
=>      |(r2)                   =>  ... => until r1==r2
    5 - 6 - 1 - 8 - 4 - 5           
        |(r1)


C++style code::
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    read1=headA
    read2=headB
    while read1!=read2:
        read1=(read1==None)?headB:read1.next
        read2=(read2==None)?headA:read2.next
    return read1    

-T/C: O(lenA+lenB) # maximum is two pass
-S/C: O(1)
'''

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        len_a=0
        cur=headA
        while cur!=None:
            len_a+=1
            cur=cur.next

        len_b=0
        cur=headB
        while cur!=None:
            len_b+=1
            cur=cur.next
            
        
        read1=headA
        read2=headB
        if len_a>len_b:
            for i in range(len_a-len_b):
                read1=read1.next
        elif len_a<len_b:
            for i in range(len_b-len_a):
                read2=read2.next
                
        while read1!=None and read2!=None:
            if read1==read2:
                return read1
            read1=read1.next
            read2=read2.next
        
        return None