Intersection of Two Linked Lists

get_intersection_node.py

"""
Description:
Write a program to find the node at which the intersection of two singly linked lists begins.
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.

Example:
Input:
A:     a1->a2 \
               +->c1->c2->c3
B: b1->b2->b3 /
Output: c1
"""

def getIntersectionNode(headA, headB):
    """
    :type head1, head1: ListNode
    :rtype: ListNode
    """
    if headA is None or headB is None:
        return None
    
    cur_a = headA
    cur_b = headB
    while cur_a != cur_b:
        cur_a = cur_a.next if cur_a else headB
        cur_b = cur_b.next if cur_b else headA
    return cur_a