O(m+n) time, O(1) space but need to temporarily modify the structure.
a1 >>> c1 >>> c3
↑

b1 >>
Method description:
 Find the length of (a1>c3), countA, and get the tail
 Find the length of (b1>c3), countB, get the tail c3, and reverse
the whole (b1>c3) link to (c3>b1)  Find the length of (a1>b1), countX
 Reverse (c3>b1) back to (b1>c3)
 If the first two tails are not equal, return None
 Proceed from a1 by (countA  (countA+countBcountX+1)/2) nodes, and
return that
It tries to count the length of the branches.
436ms in Python which is among the top 3%
class Solution:
# Count the nodes and return the tail and the length
# return (tail, len)
def countNodes(self, head):
count = 1
while head.next is not None:
count += 1
head = head.next
return (head, count)
# Count the nodes, reverse the whole link, and return the original tail and the length
# return (tail, len)
def reverseNodes(self, head):
count = 1
prev = head
now = prev.next
prev.next = None
while now is not None:
count += 1
temp = now.next
now.next = prev
prev = now
now = temp
return (prev, count)
# @param two ListNodes
# @return the intersected ListNode
def getIntersectionNode(self, headA, headB):
if headA is None or headB is None:
return None
tailA, countA = self.countNodes(headA)
tailB, countB = self.reverseNodes(headB)
_, countX = self.countNodes(headA)
self.reverseNodes(tailB)
if tailA is not tailB:
return None
for _ in range(countA  (countA+countBcountX+1)/2):
headA = headA.next
return headA