Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
编写程序以找到两个单链表开头的节点。
例如，以下两个链表：
开始在节点c1处相交。
begin to intersect at node c1.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
输入：intersectVal = 8，listA = [4,1,8,4,5]，listB = [5,0,1,8,4,5]，skipA = 2，skipB = 3
输出：值为= 8的节点的引用
输入说明：相交节点的值为8（请注意，如果两个列表相交，则此值不能为0）。从A的头部开始，它的内容为[4,1,8,4,5]。从B的头部看，它的内容为[5,0,1,8,4,5]。在A中的交叉节点之前有2个节点;在B中的交叉节点之前有3个节点。
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
输入：intersectVal = 2，listA = [0,9,1,2,4]，listB = [3,2,4]，skipA = 3，skipB = 1
输出：值为2的节点的引用
输入说明：相交节点的值为2（请注意，如果两个列表相交，则此值不能为0）。从A的头部，它读作[0,9,1,2,4]。从B的头部看，它的内容为[3,2,4]。在A中的交叉节点之前有3个节点;在B中的交叉节点之前有1个节点。
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
输入：intersectVal = 0，listA = [2,6,4]，listB = [1,5]，skipA = 3，skipB = 2
输出：null
输入说明：从A的头部，它读作[2,6,4]。从B的头部看，它的内容为[1,5]。由于两个列表不相交，因此intersectVal必须为0，而skipA和skipB可以是任意值。
说明：两个列表不相交，因此返回null。
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.
- 如果两个链接列表根本没有交集，则返回null。
- 函数返回后，链接列表必须保留其原始结构。
- 您可以假设整个链接结构中没有任何循环。
- 您的代码最好在O（n）时间内运行，并且只使用O（1）内存。
python实践
# Definition for singly-linked list.
from datashape import null
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
"""
lenA = self.getListLen(headA)
lenB = self.getListLen(headB)
if lenA > lenB:
for i in range(lenA - lenB):
headA = headA.next
elif lenA < lenB:
for i in range(lenB - lenA):
headB = headB.next
while headA != headB:
headA, headB = headA.next, headB.next
return headA
def getListLen(self, head):
length = 0
while head:
length += 1
head = head.next
return length
