160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

1. 如果两个链表没有交点，返回 None 。
2. 在返回结果后，两个链表仍须保持原有的结构。
3. 可假定整个链表结构中没有循环。
4. 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

示例：

输入1:

输出1:

ListNode(8)

输入2:

输出2:

None

解答：

def getIntersectionNode(self, headA, headB):
    if headA is None or headB is None : return None
    #合并A和B
    tempA = headA
    while(tempA and tempA.next): 
        tempA = tempA.next
    tempA.next = headB

    #检测合并之后的链表是否有环 <=> 原始两链表是否相交
    head = headA
    slow = fast = head
    steps = 0
    flag = False
    while(fast and fast.next):
        fast = fast.next.next
        slow = slow.next
        steps += 1
        if (fast == slow):
            flag = True
            break

    #无环   return之前还原A
    if not flag:
        tempA.next=None
        return None

    #有环   return之前还原A
    else:
        while(head!=slow):
            slow = slow.next
            head = head.next
        tempA.next=None
        return head