http://fulmicoton.com/posts/intersecting_link_list/ in time O(n) and memory O(1)

lca.py

#!/usr/bin/env python

class Node(object):
    def __init__(self, name, next=None):
        self.next = next
        self.name = name
        self.l = 1 if next is None else next.l + 1

    def __iter__(self,):
        cur = self
        while cur is not None:
            yield cur
            cur = cur.next

    def __str__(self):
        return self.name


def mylen(n):
    return n.l

def advance(it, n):
    '''Advance an iterator by a given number of steps'''
    for i in xrange(n):
        next(it)
    return it

def find_intersection_samelen(left, right):
    '''Just like find_intersection but lists must have equal length'''
    try:
        lhead = next(left)
        rhead = next(right)
    except StopIteration:
        return None
    if lhead == rhead:
        return lhead
    return find_intersection_samelen(left, right)

def find_intersection(left, right):
    '''Find the intersection of two linked lists'''
    llen = mylen(left)
    rlen = mylen(right)
    li = iter(left)
    ri = iter(right)
    li = advance(li, llen - min(llen, rlen))
    ri = advance(ri, rlen - min(llen, rlen))
    return find_intersection_samelen(li, ri)

if __name__ == '__main__':
    nl5 = Node('l5')
    nl4 = Node('l4', nl5)
    nl3 = Node('l3', nl4)
    nl2 = Node('l2', nl3)
    nl1 = Node('l1', nl2)
    nr3 = Node('r3', nl2)
    nr2 = Node('r2', nr3)
    nr1 = Node('r1', nr2)
    print find_intersection(nr1, nl1)