Description

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

For example, the following two linked lists:

Solution

先找到两个的长度，然后从短的那个length开始一一比较找交点

# 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
        """
        
        Acnt = 0
        Bcnt = 0
        tmp = headA
        
        while tmp is not None:
            tmp = tmp.next
            Acnt+=1
        tmp = headB
        while tmp is not None:
            tmp = tmp.next
            Bcnt+=1
        if Acnt == 0 or Bcnt ==0:
            return None
        smallcnt = min(Acnt,Bcnt)
        largecnt = max(Acnt,Bcnt)
        
        if Acnt < Bcnt:
            small = headA
            large = headB
            
        else:
            small = headB
            large = headA
        for i in range(largecnt-smallcnt):
            large = large.next
        for i in range(smallcnt):
            if small == large:
                return small
            else:
                small = small.next
                large = large.next
        return None