Intersection of Two Linked Lists

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        lenA, lenB = 0, 0
        curA, curB = headA, headB
        
        while curA:
            lenA += 1
            curA = curA.next
            
        while curB:
            lenB += 1
            curB = curB.next
        
        curA, curB = headA, headB
        
        for i in range(abs(lenA - lenB)):
            if lenA > lenB:
                curA = curA.next
            else:
                curB = curB.next
                
        # find the common node
        while curA and curB:
            if curA == curB:
                return curA
            
            curA = curA.next
            curB = curB.next
                 
        return None  

Reference

Written with StackEdit.


Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.