Intersection of two linked lists

Write a program to find the node at which the intersection of two singly linked lists begins.


In [4]:
class Node:
    def __init__(self, value=None, next=None):
        self._value = value
        self._next = next

    @property
    def value(self):
        return self._value
    
    @property
    def next(self):
        return self._next
    
    @next.setter
    def next(self, next=None):
        self._next = next

        
a0 = Node(3)
a1 = Node(2)
a2 = Node(1)
a3 = Node(0)
a0.next = a1
a1.next = a2
a3.next = a2

b0 = Node(6)
b1 = Node(5)
b2 = Node(4)
b0.next = b1
b1.next = b2
b2.next = a2

def get_list_length(head):
    if head is None:
        return 0
    
    n = 0
    while(head):
        head = head.next
        n += 1
    
    return n

def move_forward_list(head, long_len, short_len):
    move_len = long_len - short_len
    while (head and move_len > 0):
        head = head.next
        move_len -= 1
    return head

def getIntersectionNode(l0, l1):
    if l0 is None or l1 is None:
        return None
    
    l0_len = get_list_length(l0)
    l1_len = get_list_length(l1)
    #print(l0_len)
    #print(l1_len)
    
    if l0_len > l1_len:
        head0 = move_forward_list(l0, l0_len, l1_len)
        head1 = l1
    elif l0_len < l1_len:
        head0 = l0
        head1 = move_forward_list(l1, l1_len, l0_len)
    else:
        head0 = l0
        head1 = l1
    
    result = None
    while(head0 and head1):
        if head0 == head1:
            result = head0
            break
        head0 = head0.next
        head1 = head1.next

    return result

a = getIntersectionNode(a0, b0)
print(a.value)


3
4
1

In [ ]: