## 题目描述：

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.

Note:

• 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.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @param two ListNodes
# @return the intersected ListNode
if lenA == 0 or lenB == 0:
return None
hasCircle = False
cnt = 0
while p:
cnt += 1
if cnt > lenA + lenB:
hasCircle = True
break
p = p.next
if not hasCircle:
endA.next = None
return None
for x in range(lenB):
p1 = p1.next
while p1 != p2:
p1 = p1.next
p2 = p2.next
endA.next = None
return p1

while end.next:
end = end.next
return end

size = 0
while p:
size += 1
p = p.next
return size
``````

Pingbacks已关闭。