## 160. Intersection of Two Linked Lists

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

For example, the following two linked lists:

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

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return `null`.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

Thoughts:

1. Having two traversors traverse two lists separately, the total path they travel will be equal. And if a in the first round first gets the end, b will catch up with exactly shorter distance in the second round. So if there is a intersection and even two lists are not of the same length, swapping the end/ starting point in the second round will make sure they will have the same distance to the end point in the second round.

Code

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
if not headA or not headB: return None