160. Intersection of two Linked List

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

# 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
        """
        # check length of list A
        lengthA = 0
        curA = headA
        while(curA):
        	curA = curA.next
        	lengthA += 1

        # check length of list B
        lengthB = 0
        curB = headB
        while(curB):
        	curB = curB.next
        	lengthB += 1

        # move longer list's head (longLength - shortLength) steps forward
        if lengthB > lengthA:
        	curB = headB
        	for i in range(lengthB - lengthA):
        		curB = curB.next
        	curA = headA
        elif lengthA > lengthB:
        	curA = headA
        	for i in range(lengthA - lengthB):
        		curA = curA.next
        	curB = headB
        else:
        	curA = headA
        	curB = headB

        # move long / short list head together until there is an meet point
        while(curA != curB):
        	curA = curA.next
        	curB = curB.next

        # each reach its end or meet the intersection point
        if curB is None:
        	return None
        else:
        	return curB

Another interesting way to do it in O(n) time is to

1. Start from either headA or headB;

2. Reach the end of the A/B list;

3. Redirect end of A/B list to B/A start;

4. If there is intersection, a cycle linked list is promised; if there is no intersection, no cycle in the new list

5. Then entry point of cycle is the intersection point

6. Break the reference between A/B end and B/A head.