Question: https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
Question Name: Intersection of Two Linked Lists
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # Get the length of the given linked list # @param ListNodes # @return the length of the linked list def _length(self, head): current = head length = 0 while current != None: current = current.next length += 1 return length # Find the intersection node of two linked list, if it exists. # @param two ListNodes # @return the intersected ListNode or None def getIntersectionNode(self, headA, headB): lenA = self._length(headA) lenB = self._length(headB) # Make sure the list A is no longer that list B. if lenA > lenB: lenA, lenB = lenB, lenA headA, headB = headB, headA # Handle with the special case. if lenA == 0 or lenB == 0: return None # Skip the leading nodes in list B, which is impossible to be # the intersection node. currentA = headA currentB = headB for _ in xrange(lenB - lenA): currentB = currentB.next # Try to find the intersection node while currentA != None and id(currentA) != id(currentB): currentA = currentA.next currentB = currentB.next return currentA |